ACdream 1415 Important Roads
Important Roads
Problem Description
The city where Georgie lives has n junctions some of which are connected by bidirectional roads.
Every day Georgie drives from his home to work and back. But the roads in the city where Georgie lives are very bad, so they are very often closed for repair. Georgie noticed that when some roads are closed he still can get from home to work in the same time as if all roads were available.
But there are such roads that if they are closed for repair the time Georgie needs to get from home to work increases, and sometimes Georgie even cannot get to work by a car any more. Georgie calls such roads important.
Help Georgie to find all important roads in the city.
Input
The first line of the input file contains n and m — the number of junctions and roads in the city where Georgie lives, respectively (2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000). Georgie lives at the junction 1 and works at the junction n.
The following m lines contain information about roads. Each road is specified by the junctions it connects and the time Georgie needs to drive along it. The time to drive along the road is positive and doesn’t exceed 100 000. There can be several roads between a pair of junctions, but no road connects a junction to itself. It is guaranteed that if all roads are available, Georgie can get from home to work.
Output
Sample Input
6 7 1 2 1 2 3 1 2 5 3 1 3 2 3 5 1 2 4 1 5 6 2
Sample Output
2 5 7
Source
Manager
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pli pair<long long,int> 15 #define INF 0x3f3f3f3f3f3fLL 16 using namespace std; 17 const int maxn = 20100; 18 struct arc{ 19 int to,next; 20 LL w; 21 arc(int x = 0,LL y = 0,int z = -1){ 22 to = x; 23 w = y; 24 next = z; 25 } 26 }; 27 struct edge{ 28 int to,id,next; 29 edge(int x = 0,int y = 0,int z = -1){ 30 to = x; 31 id = y; 32 next = z; 33 } 34 }; 35 arc e[maxn*20]; 36 edge g[maxn*20]; 37 int head[maxn],first[maxn],ans[maxn],tot2,num; 38 int n,m,tot,x[maxn*20],y[maxn*20],z[maxn*20]; 39 int dfn[maxn],low[maxn],idx; 40 LL d[2][maxn]; 41 void add(int u,int v,LL w){ 42 e[tot] = arc(v,w,head[u]); 43 head[u] = tot++; 44 e[tot] = arc(u,w,head[v]); 45 head[v] = tot++; 46 } 47 void add2(int u,int v,int id){ 48 g[tot2] = edge(v,id,first[u]); 49 first[u] = tot2++; 50 g[tot2] = edge(u,id,first[v]); 51 first[v] = tot2++; 52 } 53 void dijkstra(int s,LL ds[maxn]){ 54 priority_queue< pli,vector< pli >,greater< pli > >q; 55 bool done[maxn] = {false}; 56 for(int i = 1; i <= n; i++) ds[i] = INF; 57 ds[s] = 0; 58 q.push(make_pair(ds[s],s)); 59 while(!q.empty()){ 60 int u = q.top().second; 61 q.pop(); 62 if(done[u]) continue; 63 done[u] = true; 64 for(int i = head[u]; ~i; i = e[i].next){ 65 if(ds[e[i].to] > ds[u] + e[i].w){ 66 ds[e[i].to] = ds[u] + e[i].w; 67 q.push(make_pair(ds[e[i].to],e[i].to)); 68 } 69 } 70 } 71 } 72 void tarjan(int u,int fa){ 73 dfn[u] = low[u] = ++idx; 74 bool flag = true; 75 for(int i = first[u]; ~i; i = g[i].next){ 76 if(g[i].to == fa && flag){ 77 flag = false; 78 continue; 79 } 80 if(!dfn[g[i].to]){ 81 tarjan(g[i].to,u); 82 low[u] = min(low[u],low[g[i].to]); 83 if(low[g[i].to] > dfn[u]) ans[num++] = g[i].id; 84 }else low[u] = min(low[u],dfn[g[i].to]); 85 } 86 } 87 int main(){ 88 while(~scanf("%d %d",&n,&m)){ 89 memset(head,-1,sizeof(head)); 90 memset(first,-1,sizeof(first)); 91 memset(dfn,0,sizeof(dfn)); 92 memset(low,0,sizeof(low)); 93 idx = num = tot2 = tot = 0; 94 for(int i = 1; i <= m; i++){ 95 scanf("%d %d %d",x+i,y+i,z+i); 96 add(x[i],y[i],z[i]); 97 } 98 dijkstra(1,d[0]); 99 dijkstra(n,d[1]); 100 LL tmp = d[0][n]; 101 for(int i = 1; i <= m; i++){ 102 int u = x[i]; 103 int v = y[i]; 104 if(d[0][u] + z[i] + d[1][v] == tmp || d[0][v] + z[i] + d[1][u] == tmp){ 105 add2(u,v,i); 106 } 107 } 108 for(int i = 1; i <= n; i++) 109 if(!dfn[i]) tarjan(i,-1); 110 printf("%d\n",num); 111 if(num){ 112 for(int i = 0; i < num; i++) 113 printf("%d%c",ans[i],i + 1 == num?'\n':' '); 114 } 115 } 116 return 0; 117 }
相关文章
- Leetcode: Word Squares && Summary: Another Important Implementation of Trie(Retrieve all the words with a given Prefix)
- Security headers quick reference Learn more about headers that can keep your site safe and quickly look up the most important details.
- Journey or destination- which is more important?
- How to override !important?
- What does !important mean in CSS?
- Six Important .NET Concepts: Stack, Heap, Value Types, Reference Types, Boxing, and Unboxing .NET中六个重要的概念:栈、堆、值类型、引用类型、装箱和拆箱
- 【翻译】Six Important .NET Concepts: Stack, Heap, Value Types, Reference Types, Boxing, and Unboxing
- Memory Access Patterns Are Important
- 视图控制器生命周期中各个重要的方法(Swift) (Important Methods during the Lifecycle of a View Controller)
- 通过!important设置css样式优先级
- CF471B MUH and Important Things
- jquery添加!important样式
- The 10 Most Important Security Controls Missing in JavaEE--reference