P1629 邮递员送信

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
vector<pair<int, int>> g[MAXN], rg[MAXN];   // 原图与反向图
int dist1[MAXN], dist2[MAXN];
bool vis[MAXN];

// 朴素 Dijkstra：n <= 1000 时 O(n^2) 足够
void dijkstra(int s, vector<pair<int, int>> adj[], int d[]) {
    fill(d, d + MAXN, INF);
    fill(vis, vis + MAXN, false);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && (u == -1 || d[v] < d[u])) u = v;
        }
        if (u == -1 || d[u] == INF) break;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (d[v] > d[u] + w) d[v] = d[u] + w;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        rg[v].push_back({u, w});
    }
    dijkstra(1, g, dist1);     // 邮局 -> 各点
    dijkstra(1, rg, dist2);    // 各点 -> 邮局：把边全部反向后再从 1 出发
    long long ans = 0;
    for (int i = 2; i <= n; i++) ans += dist1[i] + dist2[i];
    cout << ans << '\n';
    return 0;
}