Floyd 算法

众所周知，Floyd是来求最短路问题的算法

最短路径问题是图论研究中的一个经典算法问题， 指在寻找图（由结点和路径组成的）中两结点之间的最短路径。
例如：

Floyd是用了DP的思想
决策需要枚举中转点，不妨考虑也以中转点集为阶段
F[k,i,j]表示”可以经过标号≤k的点中转时”从i到j的最短路
F[0,i,j]=dis[i,j]，dis为前面定义的邻接矩阵
F[k,i,j]=min{F[k-1,i,j] , F[k-1,i,k]+F[k-1,k,j]}，O(N^3)
k这一维空间可以省略，变成F[i,j]
就成为了我们平时常见的Floyd算法
由于k是DP的阶段循环，所以k循环必须要放在最外层

---

例题：

样例

样例输入

5  7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
1 5

样例输出

60
1 4 3 5

这是一道板题，把Floyd套上就完事了

正解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 505;
int dp[MAXN][MAXN], pr[MAXN][MAXN];
int s, t;
int n, m;
void Read() {
	int i, j;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i++) {
		int A, B, C;
		scanf("%d %d %d", &A, &B, &C);
		dp[A][B] = C;
		pr[A][B] = A;
	}
}
void Write(int x) {
	if(pr[s][x] == 0)
		return;
	Write(pr[s][x]);
	printf(" %d", x);
}
int main() {
	int i, j, k;
	memset(dp, 0x3f, sizeof(dp));
	Read();
	for(i = 1; i <= n; i++)
		dp[i][i] = 0;
	for(k = 1; k <= n; k++) {
		for(i = 1; i <= n; i++) {
			for(j = 1; j <= n; j++) {
				int t = dp[i][j];
				if(dp[i][k] + dp[k][j] < dp[i][j]) {
					dp[i][j] = dp[i][k] + dp[k][j];
					pr[i][j] = pr[k][j];
				}
			}
		}
	}
	scanf("%d %d", &s, &t);
	printf("%d\n%d", dp[s][t], s);
	Write(t);
	return 0;
}