UVa|uva 10048 噪音恐惧症 Audiophobia Floyd算法图论|OJ

ljr的书里说错了，套Floyd算法的模板是，加改为max, min还是min。
还有就是ljr的if(d[i][j] < INF && d[k][j] < INF)明显是错的，应该写成if(d[i][k] < INF && d[k][j] < INF)

#include #include #include #include #define INF 99999 using namespace std; int d[10000][10000]; int main() { //freopen("ztest.txt","r",stdin); //freopen("zans.txt","w",stdout); int c, s, q; int ti = 1; while(scanf("%d%d%d", &c, &s, &q)) { if(!c && !s && !q) break; if(ti != 1) printf("\n"); printf("Case #%d\n",ti++); for(int i = 1; i <= c; i++) for(int j = 1; j <= c; j++) d[i][j] = (i == j ? 0:INF); for(int i = 0; i < s; i++) { int c1, c2, cost; scanf("%d%d%d", &c1, &c2, &cost); d[c1][c2] = d[c2][c1] = cost; } 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])); //d[j][i] = d[i][j]; } for(int i = 0; i < q; i++) { int sta, end; scanf("%d%d", &sta, &end); if(d[sta][end] == INF) printf("no path\n"); else printf("%d\n", d[sta][end]); } } return 0; }

【UVa|uva 10048 噪音恐惧症 Audiophobia Floyd算法】