The pathTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 521Accepted Submission(s): 190Special Judge
Problem Description
You have a connected directed graph.Letbe the length of the shortest path from.A graph is good if there exist.Now you need to set the length of every edge satisfy that the graph is good.Specially,if,the graph is good too.The length of one edge mustIt’s guaranteed that there exists solution.
Input
There are multiple test cases. The first line of input contains an integer, indicating the number of test cases. For each test case:The first line contains two integers n and m,the number of vertexs and the number of edges.Next m lines contain two integers each,, indicating there is a link between nodesand the direction is from.
Output
For each test case,printlines.The i-th line includes one integer:the length of edge from
Sample Input
24 61 22 41 31 22 22 34 61 22 31 42 12 12 1
Sample Output
122144113444
Author
SXYZ
Source
/* ***********************************************Author:CKbossCreated Time :2015年08月15日 星期六 12时15分02秒File Name:HDOJ5385_2.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int maxn=100100;struct P{int from,to,len;}ep[maxn];struct Edge{int to,next,id;}edge[maxn];int Adj[maxn],Size;int n,m;int Time[maxn];bool vis[maxn];void init(){memset(Time,0,sizeof(Time));memset(vis,false,sizeof(vis));memset(Adj,-1,sizeof(Adj)); Size=0;}void Add_Edge(int u,int v,int id){edge[Size].to=v;edge[Size].id=id;edge[Size].next=Adj[u];Adj[u]=Size++;}bool ans[maxn];void color(int u,int t){Time[u]=t;for(int i=Adj[u];~i;i=edge[i].next){int v=edge[i].to;int eid=edge[i].id;if(vis[v]==true) continue;ans[eid]=true;vis[v]=true;}}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T_T;scanf("%d",&T_T);while(T_T–){init();scanf("%d%d",&n,&m);for(int i=0,u,v;i<m;i++){scanf("%d%d",&u,&v);Add_Edge(u,v,i);ep[i].from=u; ep[i].to=v; ep[i].len=-1;}int ti=1;int s=1,e=n;vis[1]=true; Time[1]=1;memset(ans,false,sizeof(ans));while(s<=e){if(vis[s]) color(s++,ti++);if(vis[e]) color(e–,ti++);}for(int i=0;i<m;i++){if(ans[i]) printf("%d\n",abs(Time[ep[i].from]-Time[ep[i].to]));else printf("%d\n",n);}}return 0;}
版权声明：—– from:
，多对自己说“我能行，我一定可以”，
