图论、最短路、Floyd

使用 Floyd 求出未设置传送门时点对间的最短路后枚举所有点对 $(i,j)$ 设置传送门，每次枚举以 $i$ 和 $j$ 作中间点更新未设置传送门时的最短路，时间复杂度 $O(n^4)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],s[101][101];
long long ans;
void halffloyd(int x){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=min(a[i][j],a[i][x]+a[x][j]);
}
void restart(){
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            a[i][j]=a[j][i]=s[i][j];
}
int main(){
    ios::sync_with_stdio(0);
    memset(a,63,sizeof(a));
    cin>>n>>m,ans=1e18;
    for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++){
        static int x,y,w;
        cin>>x>>y>>w;
        a[x][y]=a[y][x]=w;
    }
    for(int i=1;i<=n;i++) halffloyd(i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) s[i][j]=a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            long long sum=0ll;
            restart();
            a[i][j]=a[j][i]=0;
            halffloyd(i);
            halffloyd(j);
            for(int k=1;k<=n;k++)
                for(int q=k+1;q<=n;q++) sum+=a[k][q];
            ans=min(ans,sum);
        }
    cout<<ans<<'\n';
    return 0;
}