题解 | 邮递员送信

#include <bits/stdc++.h>
using namespace std;
const int N=1005,M=100005;
#define INF 0x3f3f3f3f
vector<vector<pair<int,int>>> g(N,vector<pair<int,int>>());//g[u]={w,v}
vector<int>dis(N,INF);
void dijkstra(int start){
    for(int i=0;i<N;i++)dis[i]=INF;
    dis[start]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,start});
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(d>dis[u])continue;
        for(auto[w,v]:g[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pq.push({w,v});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int v,u,w;
        cin>>u>>v>>w;
        g[u].push_back({w,v});
    }
    int sum=0;
    dijkstra(1);
    for(int i=2;i<=n;i++)sum+=dis[i];
    for(int i=2;i<=n;i++){
        dijkstra(i);
        sum+=dis[1];
    }
    cout<<sum<<"\n";
}

哈!