6177 哈利波特

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

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

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

4 5

1 2 3

1 3 6

2 3 4

2 4 7

3 4 2

14

#include 
#include 
#include 
#define MAXN 105
using namespace std;
int n,m,u,v,w,g[MAXN][MAXN],f[MAXN][MAXN],ans=0x3f3f3f3f;
void Floyd(int f[MAXN][MAXN])
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
}
int floyd(int u,int v)
{
    memcpy(f,g,sizeof(g));
    int sum=0;
    f[u][v]=f[v][u]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=min(f[i][j],f[i][u]+f[u][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=min(f[i][j],f[i][v]+f[v][j]);
		}
	}
    for(int i=1;i<=n;i++)
    {
    	for(int j=i+1;j<=n;j++)
        {
        	sum+=f[i][j];
		}
	}
    return sum;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	memset(g,0x3f,sizeof(g));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		g[u][v]=g[v][u]=w;
	}
  	Floyd(g);
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			ans=min(ans,floyd(i,j));
		}
	}
 	cout<