麥克找了個新女朋友，瑪麗卡對他非常惱火並伺機報復。
因為她和他們不住在同一個城市，因此她開始准備她的長途旅行。
在這個國家中每兩個城市之間最多只有一條路相通，並且我們知道從一個城市到另一個城市路上所需花費的時間。
麥克在車中無意中聽到有一條路正在維修，並且那兒正堵車，但沒聽清楚到底是哪一條路。無論哪一條路正在維修，從瑪麗卡所在的城市都能到達麥克所在的城市。
瑪麗卡將只從不堵車的路上通過，並且她將按最短路線行車。麥克希望知道在最糟糕的情況下瑪麗卡到達他所在的城市需要多長時間，這樣他就能保證他的女朋友離開該城市足夠遠。
編寫程序，幫助麥克找出瑪麗卡按最短路線通過不堵車道路到達他所在城市所需的最長時間(用分鐘表示)。
輸入描述 Input Description第一行有兩個用空格隔開的數N和M，分別表示城市的數量以及城市間道路的數量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用數字1至N標識，麥克在城市1中，瑪麗卡在城市N中。
接下來的M行中每行包含三個用空格隔開的數A，B和V。其中1≤A，B≤N，1≤V≤1000。這些數字表示在A和城市B中間有一條雙行道，並且在V分鐘內是就能通過。
輸出描述 Output Description
輸出文件的第一行中寫出用分鐘表示的最長時間，在這段時間中，無論哪條路在堵車，瑪麗卡應該能夠到達麥克處，如果少於這個時間的話，則必定存在一條路，該條路一旦堵車，瑪麗卡就不能夠趕到麥克處。
樣例輸入 Sample Input5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
樣例輸出 Sample Output27
這道題用spfa解的話我們先跑一遍spfa來求出最短路。在此過程中呢，我們要記錄每一個點的最短路是由哪一個點走過來的（意思是沒將一個點的最短距離更新，那麼便將這個點的最短路來源換成當前點）。
接下來我們從點n開始往回找點
for(i=n;i!=1;i=p[i])//p[i]記錄的是i這個點的最短路是從哪個點走過來的 q[++c]=i; q[++c]=1;//q數組記錄的是最短路上的所有點
這段代碼記錄了最短路上所有點
接著我們進行枚舉，枚舉所有最短路上的每一條路堵車時的1——n的最短路
接著求出這些路中花費時間最長的路（因為我們考慮的是最短路的最差值）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int next,z,v;
}b[1100000];
int n,m,l[1010],d[100000],h,t,i,j,e,p[10000],q[1001],cnt,c,x,y,w,hh[2000],u,vv,ans;
bool dd[100000];
void add(int aa,int bb,int cc)
{
b[++cnt].v=bb;
b[cnt].next=hh[aa];
b[cnt].z=cc;
hh[aa]=cnt;
}
int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&w);
add(x,y,w);add(y,x,w);//鄰接表用來存邊
}
memset(l,0x3f,sizeof(l));//將每一條路的最短距離賦為最大值
l[1]=0;//起始點為點1，所以到點1的最短距離是0
x=1;
while(1)
{
if(h>t)break;
j=hh[x];
while(1)
{
e=b[j].v;
if(l[x]+b[j].z<l[e]){
l[e]=l[x]+b[j].z;
p[e]=x;
if(dd[e]==false)dd[e]=true,d[++t]=e;//dd數組記錄的是當前點是否在隊列中，如果不在就將其入隊；
}
if(b[j].next==0)break;
j=b[j].next;
}
dd[x]=false;
x=d[++h];
}
for(i=n;i!=1;i=p[i])
q[++c]=i;
ans=0;
q[++c]=1;
while(1)
{
memset(l,0x3f,sizeof(l));
l[1]=0;
u=q[i];
vv=q[++i];//u,vv記錄的是要堵車的路的兩個點
h=0;t=0;
x=1;
while(1)
{
if(h>t)break;
j=hh[x];
while(1)
{
e=b[j].v;
if((u==x&&vv==e)||(vv==x&&u==e))
{
if(b[j].next==0)break;
j=b[j].next;
continue;
}
if(l[x]+b[j].z<l[e]){
l[e]=l[x]+b[j].z;
p[e]=x;
if(dd[e]==false)dd[e]=true,d[++t]=e;
}
if(b[j].next==0)break;
j=b[j].next;
}
dd[x]=false;
x=d[++h];
}
ans=max(ans,l[n]);
if(i==c)break; //當所有最短路上的邊都枚舉過了就打斷
}
printf("%d",ans);
return 0;
}
