洛谷 P1339 [USACO09OCT] Heat Wave G

// P1339 [USACO09OCT] Heat Wave G —— ★ 这一版就能 AC
//
// 无向图上的单源最短路，只问 s 到 t 这一个数。
//
// ★ 关键的一步只有一句话：**一条无向边 = 两条方向相反的有向边**，存两遍。
//   本章讲的、证的、写的全部是有向图上的 Dijkstra，而这道题**一个结论都不用改** ——
//   因为「无向」不是 Dijkstra 的前提，它只是建图时怎么存的问题。
//   （题单那句「写完想一想为什么无向图不影响这一章的任何结论」，答案就是这一句。）
//
// ⚠ 而这句话反过来说才是这一页的重点：
//   **本章那三句证明里，一次都没有用到「边是有向的」——**
//   用到的只有「边长非负」（naive.cpp 顶上那段反证里那个 `≥ 0`）。
//   ⇒ 所以换成无向图，证明一个字不用动。
//
// 一道三十秒的算术题：n ≤ 2500、w ≤ 1000 ⇒ 任何一条简单路径 ≤ 2500 × 1000 = 2.5 × 10⁶
//   ⇒ **int 绰绰有余**，连 0x3f3f3f3f 都富余 424 倍。
//   （和隔壁 [P3371] 正好凑一对：那道题同一个常量差 2.02 倍不够用。）
//
// 复杂度 O(m log n)：顶格 m = 6200，随便跑。朴素 O(n²) = 6.25 × 10⁶ 也照样过。

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

const int INF = 0x3f3f3f3f;

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

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;
    vector<vector<PII>> 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});                 // ★ 就是这一行 —— 无向边存两遍
    }

    vector<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[s] = 0;
    q.push({0, s});
    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}); }
    }
    cout << dist[t] << '\n';
    return 0;
}

// ✗ 错法①：把无向图当成有向图 —— 每条边只存了一遍
//
// 这是这道题唯一一处**真正的**新东西，也是最容易漏的一行。
// 漏了它，算的就是另一张图上的最短路：题面给的 `u v w` 被当成「只能从 u 走到 v」。
//
// ⚠ 它不会崩、不会慢，只会安静地给出一个**偏大**的答案（少了一半的边，路只会更长）
//   —— 或者干脆走不到（打出 0x3f3f3f3f 那个 INF）。
// ★ 「答案恒 ≥ 正解」这句话是能一眼判出来的（[第 26 章那条](/sol/p1220/)：
//   给出的是一个合法方案 ⇒ 恒 ≥ 最优），度量程序里真数了一遍，300 轮一次没反过来。

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

const int INF = 0x3f3f3f3f;

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

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;
    vector<vector<PII>> 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<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[s] = 0;
    q.push({0, s});
    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}); }
    }
    cout << dist[t] << '\n';
    return 0;
}

// ✗ 错法②：邻接矩阵存图，重边**直接覆盖**（没取 min）
//
// ★ 这道题的题面**一个字都没提重边** —— 而它的**官方样例里就有两组**：
//       2 4 2  ／  2 4 3        （4 号和 2 号之间两条，一条 2 一条 3）
//       7 2 2  ／  7 2 1        （7 号和 2 号之间两条，一条 2 一条 1）
//
// ⇒ 这和隔壁 [P3371](/sol/p3371/) 正好凑成一对：
//   那道题**专门补了一句 Update** 提醒有重边，可它的官方样例里一条重边都没有（样例挡不住）；
//   这道题**题面一个字没提**，官方样例却当场就有两组。
//   ⇒ ★★ **「题面提没提」和「样例挡不挡得住」是两件独立的事**，两个方向的例子现在都有了。
//
// ⚠ 而重边只在「后来那条更长」时才真的害人（第一组是 2 → 3，正好中招）。

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

const int INF = 0x3f3f3f3f;
const int MAXN = 2505;
static int g[MAXN][MAXN];

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

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) g[i][j] = INF;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = w;                            // ⚠ 直接覆盖，后来的那条赢了
        g[v][u] = w;
    }
    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (int v = 1; v <= n; v++)
            if (g[u][v] != INF && dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v];
    }
    cout << dist[t] << '\n';
    return 0;
}

// ★ 另一条完全独立的路：从**终点** t 反着跑一次，看 dist[s]
//
// 它不是错法，是**验算的第二条路**：无向图上「s 到 t」和「t 到 s」是同一条路，
// 所以两边跑出来的数必须一模一样（度量程序里 300 轮逐个比过，0 组不同）。
//
// ⚠⚠ 而这个「显然」是有主语的 —— 主语是**这张图的边是不是无向的**：
//   [第 15 章 P1379](/sol/p1379/)（八数码，每一步都可逆）上它成立；
//   [P1135](/sol/p1135/)（电梯，步长由出发那层决定）上它**当场就错**
//   —— 那道题 10152 条边里只有 2516 条反过来也走得通。
//   ⇒ 「从终点反着跑一次」不是一个到处能用的技巧，它是**无向图**（或者反图）的特权。

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

const int INF = 0x3f3f3f3f;

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

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;
    vector<vector<PII>> 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});
    }
    vector<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[t] = 0;                                // ★ 从终点出发
    q.push({0, t});
    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}); }
    }
    cout << dist[s] << '\n';                    // ★ 读起点那一格
    return 0;
}