反正蛮水的一道题。

胡雨菲一句话让我的代码减少了10行还A了，之前的是个错的。

思路：先求出最短路，然后依次删去最短路上的每一条边，跑最短路求最大值。

关于删边：我的想法是当作链表删除，把last的next移到next，把next的last移到last，之后还要恢复。

同时还要特判last*next==0，并且要删除两条边，因为是双向的。

但是胡雨菲过来一看，说你个sb，你记录删边的两个端点，松弛时特判就行了

我：......

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 struct Edge 5 { 6     int u,v,len,next; 7 }edge[1000010];int top; 8 int dela,delb; 9 struct Point10 {11     int e,dis,from;12     bool vis;13 }point[1010];14 void add(int x,int y,int z)15 {16     top++;17     edge[top].u=x;18     edge[top].v=y;19     edge[top].len=z;20     edge[top].next=point[x].e;21     point[x].e=top;22     return;23 }24 int spfa(int k,int d,bool flag)25 {26     for(int i=1;i<=1009;i++)27     {28         point[i].dis=0x3f3f3f3f;29     }30     queue
        
         p;31     p.push(k);32     point[k].vis=1;33     point[k].dis=0;34     int op,ed,i;35     while(!p.empty())36     {37         op=p.front();38         p.pop();39         point[op].vis=0;40         i=point[op].e;41         while(i)42         {43             ed=edge[i].v;44             if((op==dela&&ed==delb)||(op==delb&&ed==dela))45             {46                 i=edge[i].next;47                 continue;48             }49             if(point[ed].dis>point[op].dis+edge[i].len)50             {51                 point[ed].dis=point[op].dis+edge[i].len;52                 if(flag) point[ed].from=i;53                 if(point[ed].vis) continue;54                 point[ed].vis=1;55                 p.push(ed);56             }57             i=edge[i].next;58         }59     }60     return point[d].dis;61 }62 int main()63 {64     int n,m,x,y,z;65     scanf("%d%d",&n,&m);66     while(m--)67     {68         scanf("%d%d%d",&x,&y,&z);69         add(x,y,z);70         add(y,x,z);71     }72     spfa(1,n,1);73 74     int e=point[n].from;75     int ans=-1;76     while(e)77     {78         dela=edge[e].u;79         delb=edge[e].v;80         ans=max(ans,spfa(1,n,0));81         e=point[edge[e].u].from;82     }83     printf("%d",ans);84     return 0;85 }