uva|uva10048
【uva|uva10048】题目描述：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22156
/*
solution:此题可以直接套上floyd算法的模板，但是要把加法改成max
对于任意一条至少包含两条边的路径，i->j，一定存在k使得i->j
噪音的最高级等于max(d[i][k], d[k][j]),但i->j路径可能并不唯一，
所以还要取一条最小的：d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
author:LinVan
time:2016/4/21
*/
#include
#include
#include
#include using namespace std;
const int maxC = 100 + 5;
const int maxS = 1000 + 5;
const int maxQ = 10000 + 5;
const int INF = 99999;
int c, s, q, d[maxC][maxC];
void floyd() {
for(int k = 1;
k <= c;
k++)
for(int i = 1;
i <= c;
i++)
for(int j = 1;
j <= c;
j++)
//if(d[i][k] < INF && d[k][j] < INF)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
}int main()
{
//freopen("input.txt", "r", stdin);
int kase = 0;
while(scanf("%d%d%d", &c, &s, &q) == 3 && c) {
for(int i = 1;
i <= c;
i++)
for(int j = 1;
j <= c;
j++) {
if(i == j)d[i][j] = 0;
elsed[i][j] = INF;
//初始化
}int a, b, val;
for(int i = 1;
i <= s;
i++) {
scanf("%d%d%d", &a, &b, &val);
d[a][b] = d[b][a] = val;
//注意数据输入是无向边
}if(kase)printf("\n");
printf("Case #%d\n", ++kase);
floyd();
//floyd主算法int u, v;
//查询
for(int i = 0;
i < q;
i++) {
scanf("%d%d", &u, &v);
if(d[u][v] == INF)printf("no path\n");
elseprintf("%d\n", d[u][v]);
}
}
return 0;
}
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长