洛谷 P3371 【模板】单源最短路径（弱化版）

// P3371【模板】单源最短路径（弱化版）—— ★ 这一版就能 AC
//
// 算法和本章 naive.cpp 一模一样（朴素 O(n²) Dijkstra，那三句话一个字没改）。
// **这一页真正要讲的，是它和本章那份代码之间那两处不起眼的差别。**
//
// ① 输出格式换了主语：本章的题面写「走不到输出 -1」，
//    这道题写的是「**若不能到达则输出 2^31−1**」。这一条对拍抓不到（两份都错就都错），
//    只能一个字一个字对着题面读。
//
// ② ★★★ 而真正会咬人的是「Σw < 2^31」这一句 ——
//    它允许一条最短路长到 **2 147 483 647**，
//    而本章 naive.cpp 里那个 `INF = 0x3f3f3f3f` 只有 **1 061 109 567**。
//    ⇒ 距离一旦越过 0x3f3f3f3f，那份代码会把一个**走得到**的点当成走不到的（见 p3371Inf3f.cpp）。
//    ⇒ 这里 `dist` 用 long long、INF 用一个真正够大的数，两个坑一起躲开。
//    （★「顶格是顶到**题面**的边上，不是顶到类型的边上」—— 第 9 章那条的又一次。）
//
// ③ 顺带一条：题面 2022/07/29 的 Update 专门提醒「两个点之间可能有多条边」。
//    ⚠ 对**邻接表**这种存法，这句话是**噪声** —— 重边原样躺在 g[u] 里，
//      松弛时那个 `<` 自己会挑短的。它只对「邻接矩阵直接赋值」那种写法是命门（p3371Mat.cpp）。
//
// 复杂度 O(n² + m)：顶格 n = 10⁴、m = 5×10⁵ ⇒ 10⁸ + 5×10⁵，本机实测 0.11 秒（时限 1 秒）。
// ⚠ 但「朴素能过」不等于「可以用邻接矩阵」：10⁴ × 10⁴ 个 int 是 400 MB，题面只给 128 MB。

#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++)
            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;
    }

    const ll UNREACH = 2147483647LL;     // ★ 2^31 − 1，题面指定的哨兵值
    for (int i = 1; i <= n; i++)
        cout << (dist[i] == INF ? UNREACH : dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错法①：把本章 naive.cpp **原样搬过来** —— INF 写成 0x3f3f3f3f
//
// ★★★ 这一份是这一页的主角，因为它**看不出哪里错了**：
//   算法一个字没改、输出格式也照题面改成了 2^31−1，
//   唯一留着的是本章那个习惯写法 `const int INF = 0x3f3f3f3f;`。
//
// 而这道题的题面写着 **Σw < 2^31** ——
//   ⇒ 一条最短路可以长到 **2 147 483 647**；
//   ⇒ 而 0x3f3f3f3f 只有 **1 061 109 567**（两者差 2.02 倍）。
//   ⇒ 距离一旦越过这条线，`dist[u] + w < dist[v]` 那个 `<` 就再也刷不动 dist[v]，
//     于是一个**明明走得到**的点，被原样当成「不可达」打出 2^31−1。
//
// ⇒ ★★ **「顶格」是顶到题面的边上，不是顶到你顺手写的那个常量上。**
//   本章那份代码没错 —— 本章的题面写着 `1 ≤ w ≤ 100`，0x3f3f3f3f 绰绰有余。
//   **换了一道题，同一个常量就成了 bug**（第 52 章「上一章的正确写法就是这一章的 bug」的又一次）。
//
// ⚠ 它在顺手随机的小数据上是**精确的 0**：权值小，距离根本够不着 1.06×10⁹。
//   要抓它必须专门造一档「权值大到贴着 Σw < 2^31」的数据（生成器档位 1）。

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

const int INF = 0x3f3f3f3f;               // ★ 本章那个习惯写法，一个字没改

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<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 (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] >= INF ? 2147483647LL : (long long)dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错法②：INF 就用题面给的那个 2^31−1（= INT_MAX），而且没有那句提前收工的 break
//
// ★ 这个坑是题面**亲手挖的**：输出格式写着「不能到达则输出 2^31−1」，
//   顺手就会想「那我把 INF 直接设成 2^31−1，最后一行连判断都不用写了」。
//
// 于是当所有还没定下来的点都是 INF 时（= 剩下的全都走不到），
// 外层那句「挑最小的」仍然会挑出一个 INF 点，接着去松弛它的邻居：
//
//     dist[u] + w  =  2147483647 + w   ← ★ int 溢出，绕回一个**负数**
//
// 负数当然比什么都小，于是一堆走不到的点被刷上了负距离。
//
// ⚠ 演示用的代码不能是未定义行为（不然换个编译器就换一种表现，第 45 章那条），
//   所以下面那一行用 unsigned 显式绕回 —— **错法一样，但可复现**。
//
// ⚠ 触发条件是**图里有走不到的点**（否则那句 break 有没有都一样）。
//   ⇒ 生成器一旦「顺手保证连通」，它就是精确的 0。

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

const int INF = 2147483647;               // ★ 题面那个哨兵值，直接拿来当 INF

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<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) break;               // ⚠ 少了 `|| dist[u] == INF`
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            int nd = (int)((unsigned)dist[u] + (unsigned)w);   // ★ 显式绕回，让这个错可复现
            if (nd < dist[v]) dist[v] = nd;
        }
    }

    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];   // INF 恰好就是要输出的 2^31−1
    return 0;
}

// ✗ 错法③：走不到的点输出 -1 —— 本章题面的格式，照抄过来了
//
// 算法完全正确，只有最后一行的哨兵值不对。
// ★ 这是本书反复说的那一类：**和算法无关，但会挂人的那一条**。
//   对拍抓得到它（因为参照物按题面输出 2^31−1），但它提醒的是另一件事：
//   **换一道题就要重读一遍输出格式**，哪怕算法一个字都不用改。
//
// ⚠ 被抓的轮数 ≡ 「这一轮里有走不到的点」的轮数 —— 一个不差（度量程序里数了）。

#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++)
            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] == INF ? -1 : dist[i]) << " \n"[i == n];   // ⚠ 本章的格式
    return 0;
}

// ✗ 错法④：用邻接矩阵存图，重边**直接覆盖**（没取 min）
//
// 题面 2022/07/29 那句 Update 就是冲着它来的：「两个点之间可能有多条边，敬请注意。」
//
// ★ 而这句话的分量，**取决于你用哪种存法**（本书第五次量到这件事）：
//   · 邻接表（p3371.cpp）：重边原样躺着，松弛时那个 `<` 自己会挑短的 ⇒ **这句话是噪声**；
//   · 邻接矩阵 + `g[u][v] = w`：后读进来的那条把前面的**盖掉了** ⇒ **这句话是命门**。
//   （正确的矩阵写法是 `g[u][v] = min(g[u][v], w)`。）
//
// ⚠ 触发条件是**两层**的：先得有重边，重边里还得是「后来的那条更长」，
//   而且被盖掉的那条还得真在某条最短路上。度量程序把这两层分开数了。
//
// ⚠⚠ 另外这一版**顶格根本开不下**：n = 10⁴ ⇒ 10⁴ × 10⁴ 个 int = **400 MB**，题面只给 128 MB。
//   ⇒ 所以这道题「朴素 O(n²) 能过」和「可以用邻接矩阵」是两句话，
//     前者成立不代表后者成立。这里把 n 限死在 2000 以内，只为了能在对拍里跑起来。

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

const ll INF = (ll)4e18;
const int MAXN = 2005;
static ll g[MAXN][MAXN];

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

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    if (n >= MAXN) { cout << "太大了，矩阵开不下\n"; 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;                     // ⚠ 直接覆盖 —— 重边里后来的那条赢了
    }

    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++)
            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];
    }
    for (int i = 1; i <= n; i++)
        cout << (dist[i] == INF ? 2147483647LL : dist[i]) << " \n"[i == n];
    return 0;
}