The path
Time Limit: 2000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 538564-bit integer IO format: %I64d Java class name: Main
Special Judge
You have a connected directed graph.Let d(x) be the length of the shortest path from 1 to x.Specially d(1)=0.A graph is good if there exist xsatisfy d(1)<d(2)<....d(x)>d(x+1)>...d(n).Now you need to set the length of every edge satisfy that the graph is good.Specially,if d(1)<d(2)<..d(n),the graph is good too.
The length of one edge must ∈ [1,n]
It's guaranteed that there exists solution.
The length of one edge must ∈ [1,n]
It's guaranteed that there exists solution.
Input
There are multiple test cases. The first line of input contains an integer T, 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, ui and vi (1≤ui,vi≤n), indicating there is a link between nodes ui and vi and the direction is from ui to vi.
∑n≤3∗105,∑m≤6∗105
1≤n,m≤105
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, ui and vi (1≤ui,vi≤n), indicating there is a link between nodes ui and vi and the direction is from ui to vi.
∑n≤3∗105,∑m≤6∗105
1≤n,m≤105
Output
For each test case,print m lines.The i-th line includes one integer:the length of edge from ui to vi
Sample Input
2 4 6 1 2 2 4 1 3 1 2 2 2 2 3 4 6 1 2 2 3 1 4 2 1 2 1 2 1
Sample Output
1 2 2 1 4 4 1 1 3 4 4 4
Source
解题：贪心
左边从2开始，右边从n开始，每次选与之前标记过的点相连的未标记过得点，该点的d[i]为该点加入的时间。最后输出时，判断该点是否在最短路上，不在的话，输出n，在的话输出d[v] - d[u]。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 301000; 4 struct arc { 5 int u,v,next; 6 arc(int x = 0,int y = 0,int z = -1) { 7 u = x; 8 v = y; 9 next = z; 10 } 11 } e[maxn]; 12 int head[maxn],p[maxn],d[maxn],tot; 13 void add(int u,int v) { 14 e[tot] = arc(u,v,head[u]); 15 head[u] = tot++; 16 } 17 void update(int u) { 18 for(int i = head[u]; ~i; i = e[i].next) 19 if(!p[e[i].v]) p[e[i].v] = u; 20 } 21 int main() { 22 int kase,n,m,u,v; 23 scanf("%d",&kase); 24 while(kase--) { 25 memset(head,-1,sizeof head); 26 memset(p,0,sizeof p); 27 scanf("%d%d",&n,&m); 28 for(int i = tot = d[0] = 0; i < m; ++i) { 29 scanf("%d%d",&u,&v); 30 add(u,v); 31 } 32 d[1] = d[n] = 1; 33 p[1] = -1; 34 int L = 1, R = n,ds = 1; 35 while(L <= R) { 36 if(p[L]) { 37 update(L); 38 d[L++] = ds++; 39 } 40 if(p[R]) { 41 update(R); 42 d[R--] = ds++; 43 } 44 } 45 for(int i = 0; i < tot; ++i) 46 printf("%d ",p[e[i].v] == e[i].u?d[e[i].v] - d[e[i].u]:n); 47 } 48 return 0; 49 }