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.

      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.

6 71 2 12 3 12 5 31 3 23 5 12 4 15 6 2

25 7

  1 #include <iostream>  2 #include <stdio.h>  3 #include <string.h>  4 #include <string>  5 #include <algorithm>  6 #include <stdlib.h>  7 #include <queue>  8 using namespace std;  9 #define M 100100 10 #define N 20020 11 #define INF 0x3fffffffff 12  13 int n,m; 14 struct node 15 { 16     int from,to,next,w,id; 17 }edge[2*M]; 18  19 struct node1 20 { 21     long long w; 22     int id; 23     bool operator < (const node1 t)const 24     { 25         return t.w<w; 26     } 27 }; 28  29 int pre[N],cnt; 30 long long int diss[N],dist[N]; 31 int que[M+10];//用循环队列怎么样 32 int ans,save[M]; 33 //然后就是找桥了 34  35 priority_queue<node1> pque; 36  37 int len[N],mark[M]; 38 int index1; 39  40 void add_edge(int u,int v,int w,int id) 41 { 42     edge[cnt].from=u; 43     edge[cnt].to=v; 44     edge[cnt].w=w; 45     edge[cnt].id=id; 46     edge[cnt].next=pre[u]; 47     pre[u]=cnt++; 48 } 49  50 void dij(long long int dis[N],int s) 51 { 52     memset(mark,0,sizeof(mark)); 53     while(pque.size()!=0) pque.pop(); 54  55     for(int i=1;i<=n;i++) 56         dis[i]=INF; 57  58     dis[s]=0; 59     node1 fi; 60     fi.id=s; 61     fi.w=0; 62     pque.push(fi); 63     //我就说， 用优先队列优化，对于稠密图基本没意义 64     node1 nwnode,cur; 65     while(pque.size()!=0) 66     { 67         cur = pque.top(); 68         pque.pop(); 69         if(mark[cur.id]==1) continue; 70         int u=cur.id; 71         mark[u]=1; 72         for(int p=pre[u];p!=-1;p=edge[p].next) 73         { 74             int v=edge[p].to; 75             if(mark[v]==1) continue; 76             if(dis[v]>cur.w+edge[p].w) 77             { 78                 dis[v]=cur.w+edge[p].w; 79                 nwnode.id=v; 80                 nwnode.w=dis[v]; 81                 pque.push(nwnode); 82             } 83         } 84     } 85 } 86  87 void spfa(long long int dis[N],int s,int t) 88 { 89     //SPFA都忘记怎么写了 90     memset(mark,0,sizeof(mark)); 91     for(int i=1;i<=n;i++) 92     { 93         dis[i]=INF; 94     } 95  96     int qf=0,qd=0; 97     que[qf]=s; 98     qf++; 99 100     dis[s]=0;101     mark[s]=1;102 103     while(qf!=qd)//作为一个循环队列，104     {105         int cur=que[qd];106         qd=(qd+1)%M;107         mark[cur]=0;108         for(int p=pre[cur];p!=-1;p=edge[p].next)109         {110             int v = edge[p].to;111             if( dis[v]>dis[cur] + edge[p].w )112             {113                 dis[v]=dis[cur]+edge[p].w;114                 if(mark[v]==0)115                 {116                     que[qf]=v;117                     qf=(qf+1)%M;118                     mark[v]=1;119                 }120             }121         }122     }123 }124 125 126 void dfs(int s)127 {128     //len[s]==-1表示没来过129 130     len[s]=index1++;131     int tmp = len[s];132     for(int p=pre[s];p!=-1;p=edge[p].next)133     {134         int v=edge[p].to;135         if( mark[edge[p].id]==1 ) continue;136 137         if(len[v]==-1)138         {139             mark[edge[p].id]=1;//把这条边标记了140             dfs(v);141             tmp=min(tmp,len[v]);142             if(len[v]>len[s])//这个就是桥143             {144                 if(len[n]!=-1)145                 {146                     if(len[1]<=len[s]&&len[n]>=len[v])147                     {148                         save[ans++]=edge[p].id;149                     }150                 }151             }152         }//无向图的桥怎么求。。。，忘光了。153         else154         {155             tmp=min(tmp,len[v]);156         }157     }158 159     len[s]=tmp;160 }161 162 int main()163 {164     scanf("%d%d",&n,&m);165     cnt=0;166     memset(pre,-1,sizeof(pre));167 168     for(int i=1;i<=m;i++)169     {170         int x,y,w;171         scanf("%d%d%d",&x,&y,&w);172         add_edge(x,y,w,i);173         add_edge(y,x,w,i);174     }175 176     //卡SPFA???177     //去你妹的178 179     //spfa(diss,1,n);180     //spfa(dist,n,1);181 182     dij(diss,1);183     dij(dist,n);184 185     long long int mi=diss[n]; //最短距离186     int tcnt = cnt;187 188     cnt=0;189     memset(pre,-1,sizeof(pre));190 191     for(int i=0;i<tcnt;i+=2)192     {193         int x,y,w,id;194         x=edge[i].from;195         y=edge[i].to;196         w=edge[i].w;197         id=edge[i].id;198         if( diss[x]+dist[y]+w ==mi || dist[x] + diss[y]+w==mi )199         {200             add_edge(x,y,w,id);201             add_edge(y,x,w,id);202         }203     }204     //构建了一个由所有可能最短路边构成的图205     memset(mark,0,sizeof(mark)); //感觉要用来记录边比较好206     memset(len,-1,sizeof(len));207     index1=0;208     ans = 0;209 210     dfs(1);211      printf("%d\n",ans);212      if(ans!=0)213     {214          for(int i=0;i<ans-1;i++)215              printf("%d ",save[i]);216         printf("%d\n",save[ans-1]);217     }218     return 0;219 }