最短路径，Floyd算法，裸题 本题要点： 1、Floyd算法复杂度 O(n^3), 适合 n <= 200 的图。 2、用邻接矩阵来存图，一方面是 Floyd算法所必须的内存空间（Floyd算法依据动态规划）， 另一方面，可以方便去掉重边。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MaxN = 110; int n, m, d[MaxN][MaxN]; void floyd() { for(int k = 1; k <= n; ++k) //k个阶段 { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } printf("%d\n", d[1][n]); } int main() { int x, y, z; while(scanf("%d%d", &n, &m) != EOF) { if(0 == n && 0 == m) break; memset(d, 0x3f, sizeof d); for(int i = 1; i <= n; ++i) d[i][i] = 0; for(int i = 1; i <= m; ++i) { scanf("%d%d%d", &x, &y, &z); d[x][y] = min(d[x][y], z); d[y][x] = min(d[y][x], z); } floyd(); } return 0; } /* 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 */ /* 3 2 */