题目描述

用张氏折边定理解析floyd为什么是k放在最外面：
k=1,代表第一次更新，因为k=1所以实际上是没有折的，就是直达
k=2,代表第二次更新，所有的更新都是用两条边更新一条边
k=3,代表第三次更新，所有的更新包括用三条边，两条边来更新，

样例

#include<iostream>
#include<cstring>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int d[N][N];

int main()
{
    int n,m;
    memset(d,0x3f,sizeof d);
    cin>>n>>m;
    for(int i=1;i<=n;i++)d[i][i]=0;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=d[b][a]=min(d[a][b],c);
    }
    for(int k=1;k<=n;k++)//为什么k要放在最上面,用张桢图论折边定理
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    int res=0;
    for(int i=1;i<=n;i++)   
        if(d[1][i]==INF){
            res=-1;
            break;
        }else{
            res=max(res,d[1][i]);
        }
    cout<<res<<endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla