UVA - 10048 Audiophobia Floyd

     思路：套用Floyd算法思想，d(i, j) = min(d(i,j), max(d(i,k), d(k,j))，就能很方便求得任意两点之间的最小噪音路径。

AC代码

#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#PRagma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> typedef long long LL;const int maxn = 100 + 5;int d[maxn][maxn];int main() {	int C, S, Q, kase = 0;	while(scanf("%d%d%d", &C, &S, &Q) == 3 && C+S+Q) {		if(kase++) printf("/n");		memset(d, inf, sizeof(d));		int x, y, cost;		for(int i = 0; i < S; ++i) {			scanf("%d%d%d", &x, &y, &cost);			d[x][y] = d[y][x] = cost; //无向图 		}		//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) {						int w = max(d[i][k], d[j][k]);						d[i][j] = min(d[i][j], w);					}				}		printf("Case #%d/n", kase);		for(int i = 0; i < Q; ++i) {			scanf("%d%d", &x, &y);			if(d[x][y] == inf) printf("no path/n");			else printf("%d/n", d[x][y]);		}	}	return 0;}如有不当之处欢迎指出！