题解 P3905 【道路重建】
斯德哥尔摩
2017-10-22 22:30:57
看了，好像没有 Floyd 的题解，来一发。。。
思路的话，与楼上差不多。。。
重点是，我用邻接表存图，结果因为一个细节，20分\*3。。。
附代码（丑陋无比。。。）：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAX 999999999//最大值
#define MAXN 110
using namespace std;
int n,m,d,s,t,a[MAXN][MAXN];
bool b[MAXN][MAXN];//道路是否被摧毁
inline int read(){//读优
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void floyd(){//Floyd 跑最短路，应该都懂吧。。。
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
printf("%d\n",a[s][t]);
}
int main(){
int u,v,w;
n=read();m=read();
for(int i=1;i<=n;i++)//赋初值
for(int j=1;j<=n;j++)
a[i][j]=(i==j)?0:MAX;
for(int i=1;i<=m;i++){//读入边
u=read();v=read();w=read();
if(a[u][v]>w)a[u][v]=a[v][u]=w;//双向边
}
d=read();
for(int i=1;i<=d;i++){//读入被摧毁的边
u=read();v=read();
b[u][v]=b[v][u]=true;//当初就是因为这里，没有考虑到边是双向的，WA 了3次。。。
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!b[i][j]&&a[i][j]!=0&&a[i][j]!=MAX)a[i][j]=0;//未被摧毁的的边权值赋为0
s=read();t=read();//读入起止点
floyd();
return 0;//结束，撒花~~~
}
```