Uva 10048 噪音恐惧症——Floyd变形

Uva 10048 噪音恐惧症——Floyd变形

d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 110;int d[maxn][maxn];int n, m, k;void init() { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } }}int main(){ int flag = 0; while (scanf("%d %d %d", &n, &m, &k) == 3 && (n || m || k)) { init(); int a, b, c; while (m--) { scanf("%d %d %d", &a, &b, &c); d[a][b] = d[b][a] = c; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int temp = max(d[i][k], d[k][j]); d[i][j] = min(d[i][j], temp); } } } if (flag++) printf("\n"); printf("Case #%d\n", flag); int x, y; while (k--) { scanf("%d %d", &x, &y); if (d[x][y] != INF) printf("%d\n", d[x][y]); else printf("no path\n"); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。