$g[i][j]$表示有了传送门之后$i$到$j$的最短路。
主要内容如下：
```cpp
for (int k=1;k<=n;k++)//标准Floyd
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]);
ans=1e9;
for (int k=1;k<=n;k++)
for (int l=k+1;l<=n;l++)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=f[i][j];
g[k][l]=g[l][k]=0;
for (int m=1;m<=n;m++)//每更新一次传送门就跑一次Floyd
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][m]+g[m][j]);
sum=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
sum+=g[i][j];
ans=min(ans,sum);
}
```
这段代码时间复杂度为$O(n^5)$，这是肯定要爆的，说明需要优化将复杂度优化为$O(n^4)$。那么该如何优化呢？
我们发现在每次更改传送门后不断在重复做$Floyd$，每个点都要当作一次中转点$m$，效率低下。既然每一次变化只改变了$k$和$l$之间的距离，我们只需要分别将$k$和$l$作为中转点来做$Floyd$。于是复杂度直接降为$O(n^4)$，完全可以AC了。
具体内容如下：
```cpp
for (int k=1;k<=n;k++)
for (int l=k+1;l<=n;l++)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=f[i][j];
g[k][l]=g[l][k]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][l]+g[l][j]);
sum=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
sum+=g[i][j];
ans=min(ans,sum);
}
```
完整代码（AC Code）
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,ans;
int f[110][110],g[110][110];
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)//初始化
for (int j=1;j<=n;j++)
if (i==j)
f[i][j]=0;
else
f[i][j]=1e9;//最大值记得开大一点
for (int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
f[u][v]=f[v][u]=w;//双向建边
}
for (int k=1;k<=n;k++)//无传送门时的最短路f数组
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]);
ans=1e9;
for (int k=1;k<=n;k++)
for (int l=k+1;l<=n;l++)
{
for (int i=1;i<=n;i++)//注意：每次更新传送门都要重置g数组
for (int j=1;j<=n;j++)
g[i][j]=f[i][j];
g[k][l]=g[l][k]=0;
for (int i=1;i<=n;i++)//k作为中转点
for (int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
for (int i=1;i<=n;i++)//l作为中转点
for (int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][l]+g[l][j]);
sum=0;
for (int i=1;i<=n;i++)//求边和
for (int j=i+1;j<=n;j++)
sum+=g[i][j];
ans=min(ans,sum);//更新最小值
}
cout<<ans<<endl;
return 0;
}
```
好了，这道题就到这儿了（点到为止）
谢谢朋友们！