【题目描述】
在哈利波特所在的巨大城堡内，有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 105using 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<