洛谷 B3647 【模板】Floyd

// ✗ 错法①：k 放到最内层 —— 三行一个字没改，只换了顺序
//
// 本章第 5 步在自己那张图上演过一次；这一页量的是它在**这道真题**上被抓多少。
// ⚠ 它不崩溃、不报错，只在「最短路要拐好几个弯、而那些弯的编号顺序不巧」时才现形。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }

    for (int i = 1; i <= n; i++)            // ✗ i、j 在外，k 在里
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    return 0;
}

// 洛谷 B3647 【模板】Floyd —— ★ 这一版就能 AC
//
// n ≤ 100 ⇒ 三重循环 10⁶ 次，本机 1 毫秒。
// 三处和「模板」二字有关的细节，每一处都在这一页有一个错误版本对照：
//   ① k 在最外层（本章第 5 步）
//   ② 无向图 ⇒ 每条边存两遍
//   ③ 重边 ⇒ 取 min，不能直接赋值
// 外加一处这道题独有的：INF 用 0x3f3f3f3f，理由不是「够大」，是 **INF + INF 不溢出**。

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

const int INF = 0x3f3f3f3f;                 // 1 061 109 567，两个加起来 2 122 219 134 < 2³¹−1
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);   // ★ 对角线要手动置 0

    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);          // ★ 重边取 min（题面明写「可能存在重边」）
        d[v][u] = min(d[v][u], w);          // ★ 无向图，存两遍
    }

    for (int k = 1; k <= n; k++)            // ★ k 是阶段，必须在最外层
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    }
    return 0;
}

// ✗ 错法②：INF 写成 INT_MAX —— ★★★ 这一页的主线
//
// 上一章（P3371 / P4779 / P1462）问的是「INF 够不够大」，答案是拿题面乘一遍。
// 这一章的 Floyd 换了一个主语：**INF + INF 会不会溢出**。
//
// Floyd 的内层是 `d[i][k] + d[k][j]`，而在中间那些层里，这两个格子**很可能都还是 INF**
// （k 这一层还没把它们连起来）。INT_MAX + INT_MAX 在 int 里绕回成 −2 ⇒
// min 会当场把这个「负距离」收下，然后顺着它一路传染出去。
//
// ⇒ 0x3f3f3f3f 的全部意义就在这儿：2 × 1 061 109 567 = 2 122 219 134 < 2 147 483 647。

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;                    // ✗ 就改了这一行
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);   // ✗ INT_MAX + INT_MAX 绕回成 −2
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    return 0;
}

// ✗ 错法④：无向图只存一遍
//
// 「存一遍还是两遍」这一行，第 32 章那张题单里演了四遍、四次答案都不一样。
// 这道题题面第一句就是「一张**无向**连通图」⇒ 必须两遍。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);          // ✗ 少了反着那一行
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    return 0;
}

// ✗ 错法⑤：对角线没置 0（整张表统一初始化成 INF）
//
// 题面要「第 i 行第 j 个整数代表从 i 到 j 的最短路径」——
// i == j 那一格的答案是 **0**，而它不是 Floyd 算出来的，是初始化时手填的。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = INF;     // ✗ 少了 i == j 那一支
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    return 0;
}

// ✗ 错法③：重边直接赋值，没取 min
//
// 题面最后一行专门加粗写着「**数据中可能存在重边**」——
// 而顺手写 `d[u][v] = w;` 的话，**后读进来的那条边会把先读进来的短边盖掉**。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = w;                        // ✗ 直接盖掉
        d[v][u] = w;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << d[i][j] << " \n"[j == n];
    return 0;
}

// ★ 另一条路：跑 n 次堆优化 Dijkstra（第 32 章那份）
//
// 它和 Floyd 一行代码都不共享 —— 所以它既是对拍的参照物，也是「该选哪个」那张表的另一半。
// 复杂度 O(n × m log m)：n = 100、m = 4500 ⇒ 约 5.4 × 10⁶，而 Floyd 是 n³ = 10⁶。
// ⚠ 本章正文说「单源问题上别用 Floyd」，这道题问的是**全源** —— 结论正好反过来。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});             // 无向图，两遍
    }
    for (int s = 1; s <= n; s++) {
        vector<int> dist(n + 1, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> 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 j = 1; j <= n; j++) cout << dist[j] << " \n"[j == n];
    }
    return 0;
}