题解 | 邮递员送信

#include <climits>
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include<functional>
#include<queue>
#include <bitset>
using ll = long long;
int n,m;
const int N = 1e3 + 7;

struct edge{
    int v;ll w;
    edge(int _v = 0,ll _w = 0):v(_v),w(_w){}
    bool operator < (const edge&u)const{
        return u.w < w;
    }
};

std::bitset<N>vis;
signed main(){
    std::cin >> n >> m;
    std::vector<std::vector<edge>>g(n + 1),rg(n + 1);
    for(int i = 0;i < m; ++i){
        int u,v;ll w;
        std::cin >> u >> v >> w;    
        g[u].emplace_back(v,w);
        rg[v].emplace_back(u,w);
    }
    auto dijkstra = [&](int st,const std::vector<std::vector<edge>>&graph){
        std::vector<int>d(n + 1,INT_MAX / 2);
        vis.reset();
        d[st] = 0;
        std::priority_queue<edge>hp;
        hp.emplace(st,d[st]);
        while(hp.size()){
            auto [u,nd] = hp.top();
            hp.pop();
            if(vis[u])continue;
            vis[u] = 1;
            for(auto [v,w]:graph[u]){
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w;
                    hp.push({v,d[v]});
                }
            }
        }
        return d;
    };
    auto d1 = dijkstra(1,g);
    auto d2 = dijkstra(1,rg);
    ll ans = 0;
    for(int i = 1;i <= n; ++i){
        ans += d1[i] + d2[i];
    }
    std::cout << ans << '\n';
}

此处确保两两可达，并且要求往返都要跑一趟，直接跑正反图dijkstra就行。