1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define MAXN 101000 6 #define MAXM 3010000 7 #define INF 214748364//注意，太大了会炸…… 8 int n,m,cnt,d[MAXN],heads[MAXN],q[MAXN],head,tail,pre[MAXN],ans,x,y,z; 9 bool viss[MAXN];10 struct node11 {12     int u,v;13     int next;14     int val;15 }edge[MAXM];16 void add(int x,int y,int z)17 {18     edge[++cnt].u=x;19     edge[cnt].v=y;20     edge[cnt].next=heads[x];21     edge[cnt].val=z;22     heads[x]=cnt;23 }24 void SPFA(bool _)//_值为true时进行的是第一遍SPFA，需要记录最短路径25 {26     head=1;tail=2;27     q[1]=1;28     viss[1]=true;29     while(head<tail)30     {31         for(int i=heads[q[head]];i!=0;i=edge[i].next)32         {33             if(d[q[head]]+edge[i].val<d[edge[i].v])34             {35                 d[edge[i].v]=d[q[head]]+edge[i].val;36                 if(_)pre[edge[i].v]=i;//记录最短路径，pre存储边的序号37                 if(!viss[edge[i].v])38                 {39                     q[tail++]=edge[i].v;40                     viss[edge[i].v]=true;41                 }42             }43         }44         viss[q[head]]=false;45         head++;46     }47 }48 void __()//枚举最短路径上的每一条边49 {50     if(x%2)y=x+1;51     else y=x-1;//相邻两条单向边记录一条双向边，x，y分别记录两条边的编号52     z=edge[x].val;53     edge[x].val=edge[y].val=INF;//设置边权为很大的值相当于删除边54     for(int i=1;i<=n;i++)d[i]=INF;55     memset(viss,false,sizeof(viss));56     d[1]=0;57     memset(q,0,sizeof(q));58     SPFA(0);59     edge[x].val=edge[y].val=z;60     if(d[n]!=INF)ans=max(d[n],ans);61     x=pre[edge[x].u];//枚举下一条边62     if(x==0)return;63     __();64 }65 int main()66 {67     scanf("%d%d",&n,&m);68     for(int i=2;i<=n;i++)d[i]=INF;69     for(int i=1;i<=m;i++)70     {71         scanf("%d%d%d",&x,&y,&z);72         add(x,y,z);73         add(y,x,z);74     }75     SPFA(1);76     ans=max(ans,d[n]);//其实可以删掉77     x=pre[n];78     __();79     printf("%d",ans);80     return 0;81 }