Problem C 最短路径（2019计算机）
Problem C 城市道路
时间限制 1000 ms 内存限制 65536 KB
题目描述
n个城市之间有若干道路，其中某些道路黑夜需要关闭，分别求出城市1到城市n白天和黑夜的最短路径。
输入格式
第一行为数据组数T 对于每组测试数据
第一行三个整数，n,m,k. （1<=n<=50）n表示城市个数，m表示道路个数，k表示黑夜需要关闭的道路个数。
接下来m行，每行 三个整数 a，b，c (1<=a,b<=n)，其中第 i 行（1<=i <=m）表示第 i
条道路为从城市a到城市b长度为c（可能存在重复边）。
接下来k行，每行一个整数w，表示黑夜要关闭的道路编号。
输出格式
每组数据输出两行
第一行为白天从城市1到城市n的最短距离
第一行为黑夜从城市1到城市n的最短距离
输入样例
1
4 4 1
1 2 1
2 3 1
3 4 1
1 4 1
4
输出样例
1
3
Floyd三层循环
#include
using namespace std;
int main(){
int T,n,m,k;
int a,b,c;
int w;
int dis[55][55];
int dis1[55][55];
int num[55][2];//记录第几条路
cin>>T;
while(T--){
cin>>n>>m>>k;
for(int i=0;i<55;i++){//初始化为不可达
for(int j=0;j<55;j++){
dis[i][j]=99999;
dis1[i][j]=99999;
}
}
for(int i=1;i>a>>b>>c;//从城市a到城市b长度为c
dis[a][b]=c;
dis[b][a]=c;
dis1[a][b]=c;
dis1[b][a]=c;
num[i][0]=a;
num[i][1]=b;
}
for(int p=1;p<=m;p++){
for(int i=1;i<=m;i++){
for(int j=1;jdis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
cout<<dis[1][n]<>w;
dis1[num[w][0]][num[w][1]]=99999;
dis1[num[w][1]][num[w][0]]=99999;
}
for(int k=1;k<=m;k++){
for(int i=1;i<=m;i++){
for(int j=1;jdis1[i][k]+dis1[k][j]){
dis1[i][j]=dis1[i][k]+dis1[k][j];
}
}
}
}
cout<<dis1[1][n]<<endl;
}
}
作者：July_zh
