Uva 10048 - Audiophobia （Floyd变形）

题目链接 https://vjudge.net/problem/UVA-10048

【题意】

输入一个C个点，S个边（C<=100,S<=1000）的无向图，边权表示该路径上的噪声值，当你从某点出发到另外一点时希望路上经过的最大噪声值最小，输入一些询问，每次询问两个点，输出这两点最大噪声值最小的路径。

【思路】

floyd算法的变型，只要设d[i][j]为从i出发，到j的最大噪声最小值，那么按照floyd算法,d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))，递推即可。

#include
using namespace std;const int inf = 100050;
const int maxn = 150;int n, m, q;
int g[maxn][maxn];
int d[maxn][maxn];void init() {for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)g[i][j] = i == j ? 0 : inf;
}void floyd() {memcpy(d, g, sizeof(d));for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));}}}
}int main() {int kase = 0;while (scanf("%d%d%d", &n, &m, &q) == 3) {if (!n && !m && !q) break;if (kase) printf("
");init();for (int i = 1; i <= m; ++i) {int u, v, c;scanf("%d%d%d", &u, &v, &c);g[u][v] = g[v][u] = c;}floyd();printf("Case #%d
", ++kase);while (q--) {int u, v;scanf("%d%d", &u, &v);if (d[u][v] != inf) printf("%d
", d[u][v]);else printf("no path
");}}return 0;
}