Floyd 算法模板

题目链接

基于动态规划的原理，f[k][i][j]表示通过前k个点从i到j的距离，转移方程f[k][i][j] = f[k-1][i][k] + f[k-1][k][j]，含义为用通过前k-1个点从i到达k的距离与通过前k-1个点从k到达j的距离 之和更新从前k个点从i到j的距离。

第一维度可以忽略。

一般采用邻接矩阵来保存边，i==j的情况为 0 0 0，其余为无穷。

注意存在负边权时，当d>INF/2，说明不可达。

#include
using namespace std;
const int N = 100;

int n, e[N][N];

int main()
{
	cin >> n;
	for (int i = 1;i  e[i][j],
	e[i][j] = (e[i][j] == 0 && i != j? 0x3f3f3f3f : e[i][j]); 
	
	for (int k = 1;k