多源最短路算法，可计算任意点对之间的最短路长度，时间复杂度\(O(n^3)\)
Floyd算法思想十分简单，用\(d[i][j]\)表示\(i\)和\(j\)节点之间的最短路，其核心代码如下：
遍历\(k\)、\(j\)、\(i\)更新即可。
题目参考：洛谷：P6464
题解：遍历传送门，然后更新所有以传送门为中继点的最短路选择
代码参考：
#include <bits/stdc++.h>
using namespace std;
int ar[105][105];
int fl[105][105];
int n, m, ans = 2e9;
inline void reset()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
fl[i][j] = ar[i][j];
}
int main()
{
cin >> n >> m;
memset(ar, -1, sizeof(ar));
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
ar[u][v] = w;
ar[v][u] = w;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (ar[i][k] != -1 && ar[k][j] != -1)
if (ar[i][j] == -1 || ar[i][j] > ar[i][k] + ar[k][j])
ar[i][j] = ar[i][k] + ar[k][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
reset();
fl[i][j] = fl[j][i] = 0;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (fl[x][y] == -1 || fl[x][y] > fl[x][i] + fl[i][y])
fl[x][y] = fl[x][i] + fl[i][y];
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (fl[x][y] == -1 || fl[x][y] > fl[x][j] + fl[j][y])
fl[x][y] = fl[x][j] + fl[j][y];
int res = 0;
for (int x = 1; x <= n; x++)
for (int y = 1; y < x; y++)
res += fl[x][y];
ans = min(ans, res);
}
}
printf("%d\n", ans);
return 0;
}