问题标题: 酷町堂：6177 哈利波特

题目描述 Description

在哈利波特所在的巨大城堡内，有n座不同的城堡。有m条不同的长桥连接着其中的某些城堡。所有教学楼直接都可以互相到达。
现在校长施展魔法，可以在任意两座城堡之间建立传送门，使得两座城堡之间的距离为0。但是只能建立一个传送门。
现在试着求出建立传送门之后，所有城堡之间的最短路径长度之和的最小值。

输入描述 Input Description

第一行，两个空格隔开的整数，n m
接下来m行，每行三个空格隔开的整数，u v w，表示u和v两个城堡之间的桥的长度是w

输出描述 Output Description

一个整数，为建立传送门之后，所有城堡之间的最短路径长度之和的最小值

TLE 33，求优化

#include<iostream>
#include<bits/stdc++.h>
#define inf (1<<25)
#define reg register
using namespace std;
int n,m,ans=inf;
int f[105][105],g[105][105];
int Floyd(int u,int v){
    for(reg int i=1;i<=n;i++)
        for(reg int j=1;j<=n;j++)
            f[i][j]=g[i][j];
    f[u][v]=f[v][u]=0;
    for(reg int k=1;k<=n;k++)
        for(reg int i=1;i<=n;i++)
            for(reg int j=1;j<=n;j++)
                f[i][j]=min(f[i][k]+f[k][j],f[i][j]);   
    int sum=0;
    for(reg int i=1;i<=n;i++)
        for(reg int j=1;j<i;j++)
            sum+=f[i][j];
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=0x3f3f3f3f;
        }
    }
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v]=g[v][u]=w;
    }
    for(reg int k=1;k<=n;k++)
        for(reg int i=1;i<=n;i++)
            for(reg int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    for(reg int u=1;u<=n;u++){
        for(reg int v=1;v<u;v++){
            ans=min(ans,Floyd(u,v));
        }
    }
    cout<<ans;
    return 0;
}