步骤	处理节点	松弛操作	dist 数组	队列
1	节点 0（dist=0）	0→1: min(∞, 0+4)=4; 0→2: min(∞, 0+2)=2; 0→3: min(∞, 0+5)=5	[0, 4, 2, 5, ∞]	{(2,2),(4,1),(5,3)}
2	节点 2（dist=2）	2→3: min(5, 2+1)=3 ← 改善！	[0, 4, 2, 3, ∞]	{(3,3),(4,1),(5,3_旧)}
3	节点 3（dist=3）	3→1: min(4, 3+1)=4（无变化）; 3→4: min(∞, 3+3)=6	[0, 4, 2, 3, 6]	{(4,1),(6,4),(5,3_旧)}
4	节点 1（dist=4）	无可松弛	[0, 4, 2, 3, 6]	{(6,4)}
5	节点 4（dist=6）	完成！	[0, 4, 2, 3, 6]	{}

最终： dist = [0, 4, 2, 3, 6]

完整 Dijkstra 实现

📄 查看代码：完整 Dijkstra 实现

// Dijkstra 算法（优先队列）— O((V+E) log V)
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;   // {距离, 节点}
typedef long long ll;

const ll INF = 1e18;          // 使用 long long 避免 int 溢出！
const int MAXN = 100005;

// 邻接表：adj[u] = {权重, v} 列表
vector<pii> adj[MAXN];

vector<ll> dijkstra(int src, int n) {
    vector<ll> dist(n + 1, INF);   // dist[i] = 到节点 i 的最短距离
    dist[src] = 0;

    // 最小堆：{距离, 节点}
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  // 取距离最小的节点

        // 关键：若已找到到 u 的更好路径则跳过（过期条目）
        if (d > dist[u]) continue;

        // 松弛 u 的所有邻居
        for (auto [w, v] : adj[u]) {
            ll newDist = dist[u] + w;
            if (newDist < dist[v]) {
                dist[v] = newDist;          // 更新距离
                pq.push({newDist, v});       // 将更新后的条目加入队列
            }
        }
    }
    return dist;
}

Dijkstra 的关键要点

🚫 关键：Dijkstra 对负边权不起作用！ 若存在负边权，Dijkstra 可能产生错误结果。算法正确性依赖于贪心假设：一旦节点从优先队列弹出（已确定），其距离就是最终的——负边破坏这个假设。对含负边权的图，改用 Bellman-Ford 或 SPFA。

Dijkstra 负边权失败原因

只对非负权重有效。 负边破坏贪心假设。
当边权较大时，距离用 long long。dist[u] + w 可能溢出 int。
用 greater<pii> 让 priority_queue 成为最小堆。
if (d > dist[u]) continue; 检查对正确性和性能至关重要。

5.4.3 Bellman-Ford 算法

当边权可以是负数时，Dijkstra 失败。Bellman-Ford 处理负边权，甚至能检测负环。

时间

O(V × E)

负边

✓ 支持

负环

✓ 可检测

核心思想：松弛 V-1 次

关键洞察：有 V 个节点的图中，任意最短路径最多使用 V-1 条边（不重复节点）。所以若松弛所有边 V-1 次，保证能找到正确的最短路径。

Bellman-Ford 含负边权的图

Bellman-Ford V-1 轮松弛过程

算法：
1. dist[src] = 0，所有其他节点 = INF
2. 重复 V-1 次：
   对每条边 (u, v, w)：
     若 dist[u] + w < dist[v]：
       dist[v] = dist[u] + w   （松弛！）
3. 检测负环：
   若还有任何边能被松弛 → 存在负环！

Bellman-Ford 实现

📄 查看代码：Bellman-Ford 实现

// Bellman-Ford 算法 — O(V * E)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int, int, int> Edge;  // {起点, 终点, 权重}

const ll INF = 1e18;

// 返回最短距离，若检测到负环则返回空数组
vector<ll> bellmanFord(int src, int n, vector<Edge>& edges) {
    vector<ll> dist(n + 1, INF);
    dist[src] = 0;

    // 松弛所有边 V-1 次
    for (int iter = 0; iter < n - 1; iter++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // 提前终止：已收敛
    }

    // 检测负环（再做一次松弛）
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            // 从源点可达的负环！
            return {};  // 表示：存在负环
        }
    }

    return dist;
}

负环检测： 负环意味着可以无限减少距离。若第 V 次松弛仍能改善某个距离，该节点在负环上或可从负环到达。

负环检测示意图

5.4.4 Floyd-Warshall 算法

用于找所有节点对之间的最短路径。

时间

O(V³)

空间

O(V²)

负边

✓ 支持

类型

全对

核心思想：通过中间节点的 DP

dp[k][i][j] = 只使用节点 {1, 2, ..., k} 作为中间节点时，从 i 到 j 的最短距离。

Floyd-Warshall DP 状态转移

递推：

dp[k][i][j] = min(dp[k-1][i][j],           // 不经过节点 k
                   dp[k-1][i][k] + dp[k-1][k][j])  // 经过节点 k

由于只需要上一层，可以折叠为二维：

📄 由于只需要上一层，可以折叠为二维：

// Floyd-Warshall 全对最短路径 — O(V^3)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXV = 505;

ll dist[MAXV][MAXV];

void floydWarshall(int n) {
    // ⚠️ 关键：k 必须是最外层循环！
    // 不变量：处理 k 之后，dist[i][j] = 只使用 {1..k} 作中间节点时 i 到 j 的最短路
    for (int k = 1; k <= n; k++) {        // ← 外层：中间节点
        for (int i = 1; i <= n; i++) {    // ← 中层：源
            for (int j = 1; j <= n; j++) { // ← 内层：目标
                // i→k→j 比直接 i→j 更快吗？
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    // Floyd-Warshall 后，若 dist[i][i] < 0 则节点 i 在负环上
}

💡 为什么 k 必须是最外层循环？ 当处理中间节点 k 时，dist[i][k] 和 dist[k][j] 必须已经用中间节点 {1..k-1} 完整计算好。若 k 在内层，这些值可能在同一轮中被更新，破坏 DP 的正确性。记住：k 是最外层，i 和 j 是内层——顺序很重要！

5.4.5 算法对比表

算法	时间复杂度	负边	负环检测	多源	最适合
BFS	`O(V + E)`	✗ 否	✗ 否	✓ 是（多源 BFS）	无权图
Dijkstra	`O((V+E) log V)`	✗ 否	✗ 否	✗（每源运行一次）	加权非负边图
Bellman-Ford	`O(V × E)`	✓ 是	✓ 是	✗	负边、检测负环
SPFA	最坏 `O(V × E)`，平均 `O(E)`	✓ 是	✓ 是	✗	稀疏图含负边
Floyd-Warshall	`O(V³)`	✓ 是	✓ 是（对角线）	✓ 是（全对）	稠密图、全对查询

如何选择？

图有负边吗？
├── 有 → Bellman-Ford、SPFA（或全对用 Floyd-Warshall）
└── 没有 → V ≤ 500 且需要全对最短路？
          ├── 是 → Floyd-Warshall  O(V³)
          └── 否 → 无权图（所有边 = 1）？
                    ├── 是 → BFS  O(V+E)
                    └── 否 → 边权只有 0 或 1？
                              ├── 是 → 0-1 BFS  O(V+E)
                              └── 否 → Dijkstra  O((V+E) log V)

5.4.6 SPFA——带队列优化的 Bellman-Ford

SPFA（最短路径快速算法） 是优化版的 Bellman-Ford，只在节点距离更新时才将其加入队列，避免冗余松弛。

⚠️ SPFA 最坏情况： SPFA 最坏时间复杂度是 O(V × E)——与朴素 Bellman-Ford 相同。在精心构造的图（竞赛中常见的「反 SPFA」测试数据）上，SPFA 会退化到 O(VE) 并 TLE。大多数随机/实际情况下很快（平均 O(E)），但对于 USACO，当所有权重非负时优先用 Dijkstra。

📄 C++ 完整代码

// SPFA（Bellman-Ford + 队列优化）
vector<ll> spfa(int src, int n) {
    vector<ll> dist(n + 1, INF);
    vector<bool> inQueue(n + 1, false);
    vector<int> cnt(n + 1, 0);   // cnt[v] = v 进入队列的次数

    queue<int> q;
    dist[src] = 0;
    q.push(src);
    inQueue[src] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;

                    // 负环检测：若节点进入队列 >= n 次
                    if (cnt[v] >= n) return {};  // 负环！
                }
            }
        }
    }
    return dist;
}

负环检测：判断全图是否存在负环

上面的 SPFA 检测的是从 src 出发可达的负环。若要判断全图是否存在负环（包含从 src 不可达的部分），需建立超级源点：

📄 C++ 完整代码

// 判断全图负环（包含不可达部分）
// 建立超级源点 0，向所有节点连 0 权边，从 0 跑 Bellman-Ford
bool hasNegativeCycle(int n) {
    // 原图节点 1..n，超级源点 0
    vector<ll> dist(n + 1, 0);  // 全部初始化为 0（等价于超级源点到所有节点距离为 0）
    vector<bool> inQueue(n + 1, true);
    vector<int> cnt(n + 1, 0);
    queue<int> q;

    // 所有节点入队（超级源点效果）
    for (int i = 1; i <= n; i++) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v); inQueue[v] = true;
                    if (++cnt[v] >= n) return true;  // 负环！
                }
            }
        }
    }
    return false;
}

5.4.7 Johnson 算法——全源最短路

Floyd-Warshall 是 O(N³)，跑 N 次 Bellman-Ford 是 O(N²M)。Johnson 算法通过重新标注边权，将 N 次 Dijkstra 应用于无负权的图，复杂度 O(NM log M)，在稀疏图上优于 Floyd。

算法步骤

建超级源点 0，向所有节点连 0 权边
用 Bellman-Ford 求 0 到所有点的最短路 h[i]（若存在负环则无解）
重新标注边权： w'(u,v) = w(u,v) + h[u] - h[v]（保证非负）
以每个点为源点跑 N 次 Dijkstra
还原答案： 实际最短路 = Dijkstra 结果 - h[s] + h[t]

📄 5. **还原答案：** 实际最短路 = Dijkstra 结果 - `h[s]` + `h[t]`

// Johnson 全源最短路 — O(NM log M)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n, m;
// adj[u] = {v, w}，edges 存所有边用于 Bellman-Ford
vector<pair<int,ll>> adj[505];
struct Edge { int u, v; ll w; };
vector<Edge> edges;

vector<ll> bellman_ford(int s) {
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    for (int i = 0; i < n; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    return dist;
}

vector<ll> dijkstra(int s, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// 返回 dist[i][j] = i 到 j 的真实最短路
// 若 i 到 j 不可达返回 INF
vector<vector<ll>> johnson() {
    // 超级源点 n+1 向所有节点连 0 权边
    for (int i = 1; i <= n; i++)
        edges.push_back({n + 1, i, 0});

    // Bellman-Ford 求势函数 h[]
    vector<ll> h = bellman_ford(n + 1);

    // 重新标注边权（保证非负）
    for (auto& e : edges) {
        if (e.u != n + 1)  // 不处理超级源点的虚拟边
            e.w += h[e.u] - h[e.v];
    }
    // 同步更新邻接表
    for (int u = 1; u <= n; u++)
        for (auto& [v, w] : adj[u])
            w += h[u] - h[v];

    // N 次 Dijkstra
    vector<vector<ll>> ans(n + 1, vector<ll>(n + 1, INF));
    for (int s = 1; s <= n; s++) {
        auto d = dijkstra(s, n);
        for (int t = 1; t <= n; t++) {
            if (d[t] != INF)
                ans[s][t] = d[t] - h[s] + h[t];  // 还原真实距离
        }
    }
    return ans;
}

💡 为什么重标后边权非负？ 三角不等式保证 h[v] ≤ h[u] + w(u,v)，因此 w'(u,v) = w(u,v) + h[u] - h[v] ≥ 0。

5.4.8 输出最短路径方案

用 pre[] 数组记录前驱节点，松弛时同步更新：

📄 用 `pre[]` 数组记录前驱节点，松弛时同步更新：

// Dijkstra 带路径输出
vector<int> dijkstra_with_path(int src, int dst, int n) {
    vector<ll> dist(n + 1, INF);
    vector<int> pre(n + 1, -1);  // pre[v] = v 的前驱
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;

    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;          // 记录前驱
                pq.push({dist[v], v});
            }
        }
    }

    // 根据 pre[] 还原路径（逆序）
    vector<int> path;
    for (int v = dst; v != -1; v = pre[v])
        path.push_back(v);
    reverse(path.begin(), path.end());

    // 检查路径是否从 src 出发
    if (path.empty() || path[0] != src) return {};  // 不可达
    return path;  // src → ... → dst
}

当所有边权为 1（无权图）时，BFS 就是用简单队列的 Dijkstra。

0-1 BFS： 当边权只有 0 或 1 时，用双端队列代替队列的强力技巧：

0-1 BFS 双端队列工作原理

双端队列：[队首 → 距离最小 ... → 队尾 → 距离最大]

松弛邻居 v（经由权重 w 的边 u→v）：
  w = 0 → push_front(v)   （与 u 距离相同——放在前面）
  w = 1 → push_back(v)    （多一步——放在后面）

💡 效率： 0-1 BFS 运行 O(V+E)——比 Dijkstra 的 O((V+E) log V) 更快。当边权只有 0 和 1 时，始终优先用 0-1 BFS。

📄 C++ 完整代码

// 0-1 BFS — O(V + E)，处理 {0,1} 权重边
vector<int> bfs01(int src, int n) {
    vector<int> dist(n + 1, INT_MAX);
    deque<int> dq;

    dist[src] = 0;
    dq.push_front(src);

    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);   // 0 权重：加到前面
                else        dq.push_back(v);    // 1 权重：加到后面
            }
        }
    }
    return dist;
}

5.4.8 网格上的 Dijkstra

许多 USACO 题目涉及网格最短路径，图是隐式的：

📄 许多 USACO 题目涉及网格最短路径，图是隐式的：

// 网格 Dijkstra — 找从 (0,0) 到 (R-1,C-1) 的最短路径
// 每个格子有进入代价
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll,int,int> tli;

const ll INF = 1e18;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

ll dijkstraGrid(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<ll>> dist(R, vector<ll>(C, INF));
    priority_queue<tli, vector<tli>, greater<tli>> pq;

    dist[0][0] = grid[0][0];
    pq.push({grid[0][0], 0, 0});

    while (!pq.empty()) {
        auto [d, r, c] = pq.top(); pq.pop();
        if (d > dist[r][c]) continue;

        for (int k = 0; k < 4; k++) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

            ll newDist = dist[r][c] + grid[nr][nc];
            if (newDist < dist[nr][nc]) {
                dist[nr][nc] = newDist;
                pq.push({newDist, nr, nc});
            }
        }
    }
    return dist[R-1][C-1];
}

⚠️ 五大经典 Dijkstra Bug

用 int 而不是 long long —— 距离和溢出 → 静默的错误答案
最大堆而非最小堆 —— 忘记 greater<pii> → 优先处理错误的节点
缺少过期条目检查（if (d > dist[u]) continue）—— 不是错误但慢约 10 倍
忘记 dist[src] = 0 —— 所有距离保持为 INF
对负边用 Dijkstra —— 未定义行为，可能无限循环或给出错误答案

本章总结

📌 核心要点

算法	复杂度	处理负边	使用场景
BFS	`O(V+E)`	✗	无权图
Dijkstra	`O((V+E) log V)`	✗	非负权重加权 SSSP
Bellman-Ford	`O(VE)`	✓	负边、检测负环
SPFA	最坏 `O(VE)`，平均快	✓	稀疏图含负边
Floyd-Warshall	`O(V³)`	✓	全对、V ≤ 500
0-1 BFS	`O(V+E)`	不适用	只有 0 或 1 权重的边

❓ 常见问题

Q1：为什么 Dijkstra 对负边不起作用？

A：Dijkstra 的贪心假设是「当前距离最短的节点不能通过后续路径改善」。有了负边，这个假设失败——通过负边的较长路径最终可能更短。结论：有负边必须用 Bellman-Ford（O(VE)）或 SPFA（平均 O(E)，最坏 O(VE)）。

Q2：SPFA 和 Bellman-Ford 有什么区别？

A：SPFA 是队列优化版的 Bellman-Ford。Bellman-Ford 每轮遍历所有边；SPFA 只更新距离被改善的节点的邻居，用队列追踪哪些节点需要处理。实践中 SPFA 快得多（平均 O(E)），但理论最坏情况相同（O(VE)）。

Q3：Floyd-Warshall 中为什么 k 循环必须在最外层？

A：这是最常见的 Floyd-Warshall 实现错误！ DP 不变量是：处理第 k 次外层循环后，dist[i][j] 表示只用 {1, 2, ..., k} 作中间节点时从 i 到 j 的最短路径。处理中间节点 k 时，dist[i][k] 和 dist[k][j] 必须已经基于 {1..k-1} 完整计算好。若 k 在内层，dist[i][k] 可能在同一轮刚被更新，导致错误结果。记住：k 在最外层，i 和 j 在内层——顺序很重要！

Q4：USACO 题目如何判断用 Dijkstra 还是 BFS？

A：关键问题：边是否有权重？

无权图（边权=1 或求最少边数）→ BFS，O(V+E)，更快更简单

加权图（不同的非负权重）→ Dijkstra

边权只有 0 或 1 → 0-1 BFS（比 Dijkstra 快，O(V+E)）

有负边 → Bellman-Ford/SPFA

Q5：什么时候用 Floyd-Warshall？

A：需要所有节点对之间的最短距离，且 V ≤ 500（O(V³) ≈ 1.25×10^8 在 V=500 时勉强可行）。典型场景：给定多个源和目标，查询任意对之间的距离。V > 500 时，对每个节点运行 Dijkstra（O(V × (V+E) log V)）更快。

🔗 与其他章节的联系

第 5.2 章（BFS 与 DFS）：BFS 是「无权图的 Dijkstra」；本章是 BFS 的直接扩展
第 5.4 章（二叉树与树算法）：树上的最短路径就是唯一的根到节点路径（DFS/BFS 够用）
第 6.1 章（DP 入门）：Floyd-Warshall 本质上是 DP（状态 = 「使用前 k 个节点」）；很多最短路变体可以用 DP 建模
USACO Gold：最短路 + DP 的组合、最短路 + 二分搜索、最短路 + 数据结构优化

练习题

题目 5.4.1 — 经典 Dijkstra 🟢 简单

题目： 给定 N 座城市和 M 条双向道路，各有行驶时间。找从城市 1 到城市 N 的最短行驶时间，若不可达输出 −1。

样例输入 1：

样例输出 1： 6（最短路：1→2→3→5，代价 2+1+3=6）

样例输入 2： 3 个城市，节点 3 不可达 → 输出： -1

💡 提示

从节点 1 做标准 Dijkstra。距离用 long long——最大路径 = N × 最大权重 = 10^5 × 10^9 = 10^14，int 会溢出。

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<ll> dist(n + 1, LLONG_MAX);
    priority_queue<pli, vector<pli>, greater<pli>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << (dist[n] == LLONG_MAX ? -1 : dist[n]) << "\n";
    return 0;
}
// 时间：O((N + M) log N)，空间：O(N + M)

题目 5.4.2 — 网格 BFS 🟢 简单

题目： 机器人从 R×C 网格的格子 (0,0) 出发，部分格子是墙（#），其余可通行（.）。找到达 (R-1, C-1) 的最少步数，不可能时输出 −1。

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    vector<string> grid(R);
    for (auto& row : grid) cin >> row;

    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    if (grid[0][0] != '#') {
        dist[0][0] = 0;
        q.push({0, 0});
    }

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    cout << dist[R-1][C-1] << "\n";
    return 0;
}

题目 5.4.3 — 负边检测 🟡 中等

题目： 给定有 N 个节点、M 条边（可能有负权重）的有向图，找从节点 1 到节点 N 的最短距离。若存在可从节点 1 到达且能到达节点 N 的负环，输出 "NEGATIVE CYCLE"。若节点 N 不可达，输出 "UNREACHABLE"。

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int,int,ll>> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;

    const ll INF = 1e18;
    vector<ll> dist(n + 1, INF);
    dist[1] = 0;

    // Bellman-Ford：V-1 遍
    for (int iter = 0; iter < n - 1; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 第 V 遍：检测负环
    vector<bool> inNegCycle(n + 1, false);
    for (int iter = 0; iter < n; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                inNegCycle[v] = true;
            }
            if (inNegCycle[u]) inNegCycle[v] = true;
        }
    }

    if (dist[n] == INF) cout << "UNREACHABLE\n";
    else if (inNegCycle[n]) cout << "NEGATIVE CYCLE\n";
    else cout << dist[n] << "\n";

    return 0;
}

题目 5.4.4 — 多源 BFS：僵尸爆发 🟡 中等

题目： K 座已感染城市同时爆发僵尸。每个时间单位，僵尸扩散到所有相邻（未感染）城市。找僵尸到达每座可达城市的最少时间，永远无法到达的城市输出 −1。

💡 提示

多源 BFS：将所有 K 座感染城市以时间 0 加入队列。然后正常运行 BFS。这等价于添加一个虚拟「超级源点」通过 0 代价边连接到所有 K 座城市。

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;

    // 将所有 K 个僵尸源以时间 0 压入
    for (int i = 0; i < k; i++) {
        int z; cin >> z;
        dist[z] = 0;
        q.push(z);
    }

    // 从所有源同时做标准 BFS
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int u = 1; u <= n; u++) {
        cout << dist[u];
        if (u < n) cout << " ";
    }
    cout << "\n";
    return 0;
}

题目 5.4.5 — Floyd 全对最短路 🟡 中等

题目： 给定 N 座城市（N ≤ 300）和 M 条道路，回答 Q 次查询：「城市 u 到城市 v 的距离在 D 以内吗？」

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    const ll INF = 1e18;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    // Floyd-Warshall：O(N³)
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int q;
    cin >> q;
    while (q--) {
        int u, v; ll D;
        cin >> u >> v >> D;
        cout << (dist[u][v] <= D ? "YES" : "NO") << "\n";
    }

    return 0;
}
// 时间：O(N³ + Q)，空间：O(N²)

题目 5.4.6 — 最大瓶颈路径 🔴 困难

题目： 给定 N 座城市和 M 条道路，每条道路有重量限制（能通过的最大货物重量）。找从城市 1 到城市 N 最大化路径最小边权的路径——即一趟能运送的最重货物。

💡 提示

修改版 Dijkstra： 不是最小化总代价，而是最大化瓶颈。dist[v] = 到 v 的任意路径的最大最小边权。用最大堆。松弛：dist[v] = max(dist[v], min(dist[u], weight(u,v)))。

✅ 完整题解

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pii>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 修改版 Dijkstra：最大化瓶颈
    vector<int> dist(n + 1, 0);
    priority_queue<pii> pq;  // 最大堆：{瓶颈, 节点}

    dist[1] = INT_MAX;
    pq.push({INT_MAX, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d < dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            int newBottleneck = min(dist[u], w);  // ← 关键：取路径上的最小值
            if (newBottleneck > dist[v]) {
                dist[v] = newBottleneck;
                pq.push({dist[v], v});
            }
        }
    }

    cout << dist[n] << "\n";
    return 0;
}
// 时间：O((N + M) log N)，空间：O(N + M)

第 5.4 章结束 — 下一章：第 6.1 章：动态规划入门

C++ 竞赛编程：USACO 学习指南