链接:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=989
题意:
输入一个C个点S条边(C≤100,S≤1000)的无向带权图,边权表示该路径上的噪声值。
当噪声值太大时,耳膜可能会受到伤害,所以当你从某点去往另一个点时,总是希望路上经过的最大噪声值最小。
输入一些询问,每次询问两个点,输出这两点间最优路径上的最大噪声值。
分析:
直接用floyd算法,但是要把加法改成max。
为什么可以这样做呢?不管是floyd算法还是dijkstra算法,都是基于这样一个事实:
对于任意一条至少包含两条边的路径i->j,一定存在一个中间点k,使得i>j的总长度等于i->k与k->j的长度之和。
对于不同的点k,i->k和k->j的长度之和可能不同,最后还需要取一个最小值才是i->j的最短路径。
把刚才的推理中“之和”换成“取最大值”,推理仍然适用。
代码:
import java.io.*;
import java.util.*;
import static java.lang.Math.*; public class Main {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
final int INF = 0x3f3f3f3f;
final int UP = 100 + 5;
int G[][] = new int[UP][UP]; void MAIN() {
for(int cases = 1; ; cases++) {
int c = cin.nextInt();
int s = cin.nextInt();
int q = cin.nextInt();
if(c + s + q == 0) break;
for(int i = 0; i < c; i++) {
G[i][i] = 0;
for(int t = i+1; t < c; t++) G[i][t] = G[t][i] = INF;
}
for(int f, b, v, i = 0; i < s; i++) {
f = cin.nextInt() - 1;
b = cin.nextInt() - 1;
v = cin.nextInt();
G[f][b] = G[b][f] = min(G[b][f], v);
} for(int k = 0; k < c; k++) {
for(int i = 0; i < c; i++) {
for(int j = 0; j < c; j++) {
G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));
}
}
} if(cases > 1) System.out.println();
System.out.printf("Case #%d\n", cases);
for(int f, b, i = 0; i < q; i++) {
f = cin.nextInt() - 1;
b = cin.nextInt() - 1;
if(G[f][b] == INF) System.out.println("no path");
else System.out.println(G[f][b]);
}
}
} public static void main(String args[]) { new Main().MAIN(); }
}