洛谷 P1629 邮递员送信

// P1629 邮递员送信 —— ★ 这一版就能 AC
//
// 题意翻译成两句话：
//   答案 = Σ dist(1 → i) ＋ Σ dist(i → 1)      （i = 2 … n）
//   前一半是一次普通的单源最短路；★ 后一半才是这道题的**关键一步**。
//
// ★ 关键的一步：**把所有边反过来，建一张反图，在反图上从 1 号跑一次**。
//   为什么对：反图上「1 → i」的每一条路，把它逐条边反过来，
//   就是原图上一条「i → 1」的路，长度一模一样 ⇒ 两个集合一一对应 ⇒ 最短的那条也对应。
//   ⇒ **一次 Dijkstra 就算完了全部 n−1 个「回程」**，而不是跑 n 次。
//
// ⚠⚠ 而这道题和上一道 [P1339] 正好构成一对反面：
//   P1339 是无向图，那一行 `g[v].push_back({u, w})` 是**必须写的**；
//   这道题「所有的道路都是单行的」，**写了那一行当场就错**。
//   ⇒ 第 52 章那条「上一章的正确写法就是这一章的 bug」，在**同一张题单里**又演了一次
//     （上一次是第 27 章 P2016 / P1352 的编号基）。
//
// ⚠ 一道三十秒的算术题：n ≤ 1000、w ≤ 10⁴ ⇒ 单条最短路最长 999 × 10⁴ ≈ 10⁷；
//   要加 2 × 999 个这样的数 ⇒ 答案能到 **2 × 10¹⁰**，而 int 只到 2.1 × 10⁹。
//   ⇒ **必须 long long**（p1629Int.cpp 把这条线量出来了）。
//
// 复杂度 O(m log n) × 2，顶格 m = 10⁵ ⇒ 本机 0.01 秒。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

/* 在给定的邻接表上从 1 号跑一次 Dijkstra，返回 dist[] */
static vector<ll> dij(const vector<vector<pair<int, int>>>& g, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, int>>> g(n + 1), rg(n + 1);
    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});                 // ★ 反图：同一条边，两头调过来
    }

    vector<ll> a = dij(g, n), b = dij(rg, n);
    ll ans = 0;
    for (int i = 2; i <= n; i++) ans += a[i] + b[i];
    cout << ans << '\n';
    return 0;
}

// ✗ 错法②：把图当成无向图存 —— ★ 上一道题 [P1339] 的**正确写法**，在这儿就是 bug
//
//     g[u].push_back({v, w});
//     g[v].push_back({u, w});     <- P1339 必须写这一行；这道题写了它当场就错
//
// 题面：「由于这个城市的交通比较繁忙，因此**所有的道路都是单行的**」。
// 多存那一遍等于凭空造出一堆反向道路 ⇒ 路只会更短 ⇒ ★ **答案恒 ≤ 正解**
//   （[第 26 章那条判据](/sol/p1220/)：解的是一个**放宽了**的问题 ⇒ 恒 ≤ 最优。
//    度量程序里 300 轮一次没反过来。）
//
// ⇒ ★★ 这是本书那条「**上一章的正确写法就是这一章的 bug**」在**同一张题单里**的现场
//   （第 52 章 `fa[root] = root`、第 27 章 P2016 / P1352 的编号基之后，第三次）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

static vector<ll> dij(const vector<vector<pair<int, int>>>& g, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});                  // ⚠ 多存的这一遍就是 bug
    }
    vector<ll> a = dij(g, n);
    ll ans = 0;
    for (int i = 2; i <= n; i++) ans += a[i] * 2;   // 无向图上去程 = 回程，于是也就乘 2
    cout << ans << '\n';
    return 0;
}

// ✗ 错法①：以为「回程 = 去程」，把去程那一半直接乘 2
//
// 这是最顺手的第一反应 —— 而它是**无向图的思维**。
// 题面白纸黑字写着「**所有的道路都是单行的**」：
// 从 1 走到 i 花 5，从 i 走回 1 完全可以花 50，也可以走另一条完全不同的路。
//
// ⚠ 它的方向是可判的：回程的最短路 ≥ 0，而去程 × 2 = 去程 + 去程 ——
//   两者谁大谁小**不一定**（度量程序里两个方向都数了）。
//   ⇒ 这一条和 [P1339] 那个「只存一遍边恒 ≥ 正解」不一样：**这个错法两头都会跑偏。**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    ll ans = 0;
    for (int i = 2; i <= n; i++) ans += dist[i] * 2;      // ⚠ 就是这个 × 2
    cout << ans << '\n';
    return 0;
}

// ✗ 错法③：答案用 int 累加
//
// 一道三十秒的算术题：
//   n ≤ 1000、w ≤ 10⁴ ⇒ 一条最短路最长 999 × 10⁴ ≈ 10⁷；
//   要加 2 × (n−1) = 1998 个这样的数 ⇒ **答案能到 2 × 10¹⁰**，而 int 只到 2 147 483 647。
//
// ⚠ 而这个上界不是纸上谈兵：一个**单向环** 1 → 2 → … → n → 1、每条边都 10⁴，
//   答案正好是 10⁴ × n(n−1) ≈ 10¹⁰ —— 生成器档位 1 造的就是它，
//   实测顶格答案 **9 990 000 000**，是 int 上限的 **4.65 倍**。
//
// ⚠ 演示用的代码不许是未定义行为（第 45 章那条），所以这里用 unsigned 显式绕回。
// ★ 顺带：dist 本身（10⁷）在 int 里绰绰有余 —— **撑破的是「把它们加起来」那一步**。
//   ⇒ 「要不要 long long」问的从来不是「这道题的数大不大」，而是「**哪一个量**会大」。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

static vector<ll> dij(const vector<vector<pair<int, int>>>& g, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, int>>> g(n + 1), rg(n + 1);
    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});
    }
    vector<ll> a = dij(g, n), b = dij(rg, n);
    unsigned ans = 0;                             // ⚠ 32 位；用 unsigned 让绕回可复现
    for (int i = 2; i <= n; i++) ans += (unsigned)a[i] + (unsigned)b[i];
    cout << (int)ans << '\n';
    return 0;
}