codevs1021 玛丽卡
题目描述 Description
麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。因为她和他们不住在同一个城市，因此她开始
准备她的长途旅行。在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另
一个城市路上所需花费的时间。麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清
楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。玛丽卡将
只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在
的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。编写程序，帮助麦克找出玛丽卡
按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入描述 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 Input
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例输出 Sample Output
27
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n,m; 6 int cnt,start,end,ans; 7 int head[1010],q[30050],dis[1010],p[1000010]; 8 bool vis[1010]; 9 struct node{ 10 int u; 11 int v; 12 int w; 13 int next; 14 }s[1000010]; 15 16 void add(int x,int y,int z){//建边 17 s[++cnt].u=x; 18 s[cnt].v=y; 19 s[cnt].w=z; 20 s[cnt].next=head[y]; 21 head[y]=cnt; 22 } 23 24 int main(){ 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=m;i++){ 27 int x,y,z; 28 scanf("%d%d%d",&x,&y,&z); 29 add(x,y,z); 30 add(y,x,z);//无向图双向建边 31 } 32 33 dis[1]=0;//1--1 dis=0 34 vis[1]=true; 35 for(int i=2;i<=n;i++) dis[i]=999999999; 36 q[++start]=1;//1进队 37 end++; 38 39 while(start<=end){//spfa 40 for(int i=head[q[start]];i!=0;i=s[i].next){ 41 if(dis[q[start]]+s[i].w<dis[s[i].u]){//松弛 42 dis[s[i].u]=dis[q[start]]+s[i].w; 43 p[s[i].u]=i;//记录路径 44 if(vis[s[i].u]==false){//判断是否进队 45 q[++end]=s[i].u; 46 vis[s[i].u]=true; 47 } 48 } 49 } 50 vis[q[start++]]=false;//队首弹出 51 } 52 53 ans=max(ans,dis[n]);//不删边的情况下最优解 54 55 int t=n,k; 56 while(t!=0){//枚举删除最优路径上那一条边 57 k=s[p[t]].w;//删边记录删除路径 val 58 s[p[t]].w=999999999;//相当于删除 59 if(p[t]&1)s[p[t]+1].w=999999999;//双向建 双向删 60 else s[p[t]-1].w=999999999; 61 for(int i=2;i<=n;i++){ 62 dis[i]=999999999; 63 vis[i]=false; 64 } 65 for(int i=2;i<=end;i++)q[i]=0; 66 dis[1]=0; 67 vis[1]=true; 68 start=1; 69 end=1; 70 q[start]=1; 71 72 while(start<=end){//删一边 spfa 73 for(int i=head[q[start]];i!=0;i=s[i].next){ 74 if(dis[q[start]]+s[i].w<dis[s[i].u]){ 75 dis[s[i].u]=dis[q[start]]+s[i].w; 76 if(vis[s[i].u]==false){ 77 q[++end]=s[i].u; 78 vis[s[i].u]=true; 79 } 80 } 81 } 82 vis[q[start++]]=false; 83 } 84 85 if(dis[n]!=999999999)ans=max(ans,dis[n]); 86 s[p[t]].w=k;//复原 87 if(p[t]&1)s[p[t]+1].w=k; 88 else s[p[t]-1].w=k; 89 t=s[p[t]].v; 90 } 91 printf("%d",ans); 92 return 0; 93 }