多元最短路——Floyd
思路：枚举起点终点和中转点
变量：
int m, dis[N][N], n;
m条边，n个点，dis[i][j]数组储存从i到j的最短路径
主体：
void Folyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; return; }
分解一下。。。
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for循环枚举从i到j的路径
枚举中转点
for (int k = 1; k <= n; k++)
完整代码：
#include <iostream> #include <cstdio> #define N 1001 #define INF 233 int m, dis[N][N], n; void Folyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; return; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { dis[i][j] = INF; if (i == j) dis[i][j] = 0; } for (int i = 1; i <= m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); dis[a][b] = c; } Folyd(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { printf("%5d", dis[i][j]); } printf("\n\n"); } return 0; }
原文：https://www.cnblogs.com/mynygtfl/p/11443801.html