题解 | 邮递员送信

单元最短路 Dijkstra算法解决，数据范围较小，朴素版即可解决O(n²）（因为我只会朴素版）

#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
const int INF=1e18;
void solve(){
    int n,m;cin>>n>>m;
    vector<vector<int>> val(n+1,vector<int>(n+1,INF)),val2(n+1,vector<int>(n+1,INF));
    vector<int> d(n+1,INF),d2(n+1,INF);
    vector<bool> vis(n+1,false),vis2(n+1,false);
    d[1]=d2[1]=0;
    while(m--){
        int u,v,w;cin>>u>>v>>w;
        val[u][v]=w;
        val2[v][u]=w;
    }
    for(int i=1;i<=n;i++){
        int u=-1,minn=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&d[j]<minn){
                u=j;
                minn=d[j];
            }
        }
        if(u==-1) break;
        vis[u]=true;
        for(int k=1;k<=n;k++){
            if(!vis[k]&&val[u][k]<INF){
                d[k]=min(d[k],d[u]+val[u][k]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        int u=-1,minn=INF;
        for(int j=1;j<=n;j++){
            if(!vis2[j]&&d2[j]<minn){
                u=j;
                minn=d2[j];
            }
        }
        if(u==-1) break;
        vis2[u]=true;
        for(int k=1;k<=n;k++){
            if(!vis2[k]&&val2[u][k]<INF){
                d2[k]=min(d2[k],d2[u]+val2[u][k]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=d[i]+d2[i];
    }
    cout<<ans;
} 
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}