♠ use C++11
是一种求多源最短路的算法，但复杂度较高，为 \(\mathcal{O}(n^3)\)，不过常数较小，编码简单。（只有 3 个 ）for
我们设三个节点 \(k,u,v\)，我们求 \(u\) 到 \(v\) 的最短路，可以找出中间结点 \(k\)，将问题转化成 \(u\) 到 \(k\) 再到 \(v\) 的最短路，即：\(u\) 到 \(v\) 的最短路等于 \(u\) 到 \(k\) 的最短路加上 \(k\) 到 \(v\) 的最短路。
设 \(f_{u,v}\) 表示 \(u\) 到 \(v\) 的最短路，在最开始每个节点之间的最短路都不知道，我们算作无限，后面根据题意建立边，边上的两点肯定为最短路。然后，根据上述推论，可得 \(f_{u,v}=f_{u,k}+f_{k,v}\)。
当然，Floyd 需要保证有最短路，即图中不能存在负环。
下面就是代码。
//有向边的Floyd
int f[MAXN][MAXN],n,m;
memset(f,0x3f,sizeof f);
cin>>n>>m;
int a,b,w;
for(int i=1;i<=m;i++)
cin>>a>>b>>w,f[a][b]=w;
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
f[u][v]=min(f[u][v],f[u][k]+f[k][v]);
//f[i][j]即为i到j的最短路，若f[i][j]=0x3f3f3f3f，那么i与j不成通路