参考：https://blog.csdn.net/qq_35644234/article/details/60875818

一.Floyd算法的介绍

    1.算法的特点：

    弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图或负权（仅适合权值非负的图)的最短路径问题，同时也被用于计算有向图的传递闭包。

    2.算法的思路：

　　通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P（记录最短路的路径需要，若题目不需要求路径则不需要P数组）中的元素b[i][j]，表示顶点i到顶点j经过了顶点b[i][j]。

　　假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。实质上是背包DP问题，最外层循环是k，表示利用前k个作为中间计算a[i][j]的最小值，本来需要三位数组a[k][i][j]，因为第k次循环只会用到a[k-1][i][j]，所以利用滚动数组，使用二维数组即可。更新N次之后，操作完成！时间复杂度为O(N^3)，空间复杂度为O(N^2)。

　　核心代码：

1     for(k=0;k
     
      a[i][k]+a[k][j])5                      a[i][j]=a[i][k]+a[k][j],b[i][j]=b[i][k];
     

　　只有5行！现在你会发现这个看起来很高大上的算法很简单了，算是最短路的4个算法里最暴力的了！

　　3.实例：

　　题目链接：https://pintia.cn/problem-sets/1101307589335527424/problems/type/7

　　题意：有n种动物，m种直接转换的咒语，且转换具有传递性，求从哪一种动物到另一种的动物的最长咒语的最小值，若不能转换到所有动物，则输出0.

　　思路：Floyd算法的裸应用，将动物抽象为点，咒语长度抽象为边的权值，代码如下：

#include
     
      using namespace std;const int inf=0x3f3f3f3f;int n,m,a,b,c;int mp[105][105];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i)        for(int j=1;j<=n;++j)            if(i!=j) mp[i][j]=inf;    while(m--){        scanf("%d%d%d",&a,&b,&c);        mp[a][b]=c;        mp[b][a]=c;    }    for(int k=1;k<=n;++k)        for(int i=1;i<=n;++i)            for(int j=1;j<=n;++j)                if(mp[i][j]>mp[i][k]+mp[k][j])                    mp[i][j]=mp[i][k]+mp[k][j];    int maxi,minv=0,res=inf;    for(int i=1;i<=n;++i){        maxi=0;        for(int j=1;j<=n;++j)            if(mp[i][j]>maxi)                 maxi=mp[i][j];        if(maxi