最短路径Floyd算法 题目意思： n个点，m条有向边， 每条边都有一个长度。 从点x 到 点y，有一条路径的话，最长的那一段距离表示这条路径的花费。 求任意两点之间的最小花费。 本题要点： 1、n <= 300, 可以用 floyd 算法，求任意两点之间的最小花费。 原来的路径是累加起来的，现在只需要记录，这条路径的最大长度即可。 2、 点 i 经过 点 k ，然后到达点 j. 那么，d[i][j] = min(d[i][j], max(d[i][k], d[k][j])), 前提是， i 和 k 点必须连通的， k 和 j 点也是必须连通的(d[i][k] < INF， d[k][j] < INF)。 不然 max(d[i][k], d[k][j]) == INF ,求出来 d[i][j] == INF, 如果 i 和 j 原来是连通的，就出错了。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MaxN = 310, INF = 0x7fffffff; int d[MaxN][MaxN]; int n, m, query; void floyd() { for(int k = 1; k <= n; ++k) { for(int i = 1; i <= n; ++i) { if(d[i][k] < INF) for(int j = 1; j <= n; ++j) { if(d[k][j] < INF) { int tmp = max(d[i][k], d[k][j]); if(d[i][j] > tmp) { d[i][j] = tmp; } } } } } } int main() { int x, y, z; scanf("%d%d%d", &n, &m, &query); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) d[i][j] = INF; for(int i = 1; i <= m; ++i) { scanf("%d%d%d", &x, &y, &z); d[x][y] = z; } floyd(); for(int i = 0; i < query; ++i) { scanf("%d%d", &x, &y); if(d[x][y] == INF) { printf("-1\n"); }else{ printf("%d\n", d[x][y]); } } return 0; } /* 5 6 3 1 2 12 3 2 8 1 3 5 2 5 3 3 4 4 2 4 8 3 4 1 2 5 1 */ /* 4 8 -1 */