link

首先我们要明白，floyed的本质上是一个dp，那么显然我们要先跑一边floyed，然后进行更新

当我们更新的两个点之间的距离的时候，显然我们改变的是和它们有关的距离，所以只要更新这两个边就可以了.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int n,m;
int x,y,w;
int ans=99999999999;
int g[101][101];
int f[101][101];
int tem;
void ini(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            f[i][j]=g[i][j];
        }
    }
    tem=0;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&w);
        g[x][y]=g[y][x]=w;
    }
    for(int i=1;i<=n;++i){
        g[i][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                g[j][k]=min(g[j][k],g[j][i]+g[i][k]);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            f[i][j]=g[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<i;++j){
            ini();
            f[i][j]=f[j][i]=0;
            for(int k=1;k<=n;++k){
                for(int z=1;z<=n;++z){
                    f[k][z]=min(f[k][z],f[k][i]+f[i][z]);
                }
            }
            for(int k=1;k<=n;++k){
                for(int z=1;z<=n;++z){
                    f[k][z]=min(f[k][z],f[k][j]+f[j][z]);
                }
            }
            for(int k=1;k<=n;++k){
                for(int z=1;z<k;++z){
                    tem+=f[k][z];
                }
            }
            ans=min(ans,tem);
        }
    }
    cout<<ans;
    return 0;
}