洛谷 P4779 【模板】单源最短路径（标准版）

// P4779【模板】单源最短路径（标准版）—— ★ 这一版就能 AC
//
// ★ 这道题和 [P3371] 的题面**几乎一字不差**，变的只有数据范围那几行：
//
//        P3371             P4779
//   n    ≤ 10⁴             ≤ 10⁵          ← ★ 朴素 O(n²) 从 10⁸ 变成 10¹⁰
//   m    ≤ 5×10⁵           ≤ 2×10⁵
//   Σw   < 2³¹             ≤ 10⁹          ← ★ 这一行把「INF 该写多大」整个翻了面
//   s    任意              固定是 1
//   可达  可能走不到        **保证都走得到**
//
// ⇒ 于是「哪一版该交」在这两道题上给出**相反**的答案：
//   P3371 朴素 0.13 秒随便过；这道题朴素 10¹⁰ 次，本机 22.3 秒 —— 只有堆优化能过。
//   （第 22 章 B3637 / P1020 那条「哪一版该交由题面的 n 说了算」的又一次现场。）
//
// ★ 而最值钱的一条对照在 INF 上：
//   题面 `0 ≤ Σw ≤ 10⁹` ⇒ 任何一条最短路都 ≤ 10⁹ < 0x3f3f3f3f = 1 061 109 567，
//   ⇒ **同一个 `INF = 0x3f3f3f3f`，在 P3371 上必错、在这道题上恰好安全 —— 余量只有 6.1%。**
//   下面仍然用 long long，理由是「不必去记那 6.1%」；p4779Inf3f.cpp 把那一版也留着，
//   实测 300 轮和它逐字节相同。

#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, s;
    if (!(cin >> n >> m >> s)) 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[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}); }
    }

    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];      // 题面保证都走得到，不用管哨兵值
    return 0;
}

// ⚠ 朴素 O(n²) Dijkstra —— **答案永远是对的，可它在这道题上跑不完**
//
// 一个字都没改地从 [P3371] 那一页搬过来（那儿它 0.13 秒随便过）。
// 这道题 n ≤ 10⁵ ⇒ 外层挑 n 次、每次扫 n 个点 = **10¹⁰** 次比较。
//
// 本机实测（顶格 n = 10⁵）：**22.3 秒**，时限 1 秒。
//
// ⇒ ★★ 这是本书那条「[官方样例和对拍都筛不出「答案对但跑不完」](/sol/p5019/)」的又一次：
//   它和正解**逐字节相同**，对拍 300 轮 0 不一致 —— 唯一能发现它的办法是
//   **数一数那个 n² 是多少**，或者真去跑一次顶格。

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

const ll INF = (ll)4e18;

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

    int n, m, s;
    if (!(cin >> n >> m >> s)) 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);
    vector<int> vis(n + 1, 0);
    dist[s] = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)             // ★ 就是这一行，n 次 × n 个点
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}

// ★ 「INF 写成 0x3f3f3f3f、dist 用 int」—— 在这道题上它是**对的**
//
// 同一个写法在 [P3371] 那一页是本页主角级的 bug（那道题 Σw < 2³¹，距离能到 2 147 483 647）。
// 这道题的题面写着 **0 ≤ Σw ≤ 10⁹**：
//
//     任何一条最短路的长度 ≤ Σw ≤ 1 000 000 000 < 0x3f3f3f3f = 1 061 109 567
//
// ⇒ 它**恰好够**，而余量只有 **6.1%**。
//   （这也是「[答案 ≥ 任何一个被用到的中间值](/sol/p1164/)」那条论证模式的第四次登场：
//     被松弛出来的每一个值都是某条路的长度，所以它们全在 Σw 以内。）
//
// ★ 这一页留着它，是为了把那句结论钉死：
//   **「INF 该写多大」不是一个能背的常量，是一道要拿题面乘一遍的算术题** ——
//   同一个 0x3f3f3f3f，隔壁那道题上必错，这道题上一分不扣。

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

const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;

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

    int n, m, s;
    if (!(cin >> n >> m >> s)) 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}); }
    }
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}

// ⚠ SPFA（队列优化的 Bellman–Ford）—— ★ 这道题的**题目背景**就是冲着它写的
//
// 原题背景原文：「2018 年 7 月 19 日，某位同学在 NOI Day1 T1 里非常熟练地使用了
// 一个广为人知的算法求最短路。然后呢？100 → 60；Ag → Cu。」
//
// SPFA 的答案**永远是对的**（它就是 Bellman–Ford，只是不去松弛那些没变过的点）。
// 它的问题只在**次数**上：一个点可以被反复入队，最坏是 O(nm)。
//
// ★ 而「最坏」不是随机数据能撞出来的（本书第三次撞见这件事，
//   前两次是 [P3916] 的 0.23 秒 vs 36.35 秒、[P1141] 的 683 格 vs 10⁶ 格）——
//   要**造对形状**：网格图（横边很短、竖边很长）能让 SPFA 反复回头改。
//   p4779Grid.cpp 就是那个形状，正文第 ⑤ 步把倍数列出来了。
//
// 这一份用 `deque` 的朴素写法（不做 SLF/LLL 优化），因为要演示的正是它的最坏情形。

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

const ll INF = (ll)4e18;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool countMode = (argc > 1 && string(argv[1]) == "count");   // 只打「出队了多少次」

    int n, m, s;
    if (!(cin >> n >> m >> s)) 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);
    vector<char> inq(n + 1, 0);
    deque<int> q;
    dist[s] = 0;
    q.push_back(s);
    inq[s] = 1;
    ll pops = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        inq[u] = 0;
        pops++;                                   // ★ 这就是那把机器无关的尺子
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push_back(v); }
            }
    }

    if (countMode) { printf("出队 %lld 次\n", pops); return 0; }
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}