单源最短路：Bellman-Ford、Dijkstra、SPFA等算法 | 王心俊老师信息学奥赛课件

板块	核心内容	对应大纲
松弛与分类	单源 / 多源；正权 / 负权；松弛操作定义	【6】单源最短路
Bellman-Ford	n−1 轮全边扫描；第 n 轮检测负环；O(nm)	【6】Bellman-Ford
SPFA	队列优化；入队次数 ≥ n 判负环；平均快、最坏 O(nm)	【6】SPFA
Dijkstra	非负权前提；朴素 O(n²) 与堆优化 O(m log n)	【6】Dijkstra
存图	链式前向星、vector 邻接表	【5】图的基本存储

模块 02

知识探究

先看松弛操作这个共同底座，再逐个拆解三种算法的适用条件与实现细节。

1最短路问题分类与松弛操作共同底座

问题类型	含义	典型算法	复杂度参考
单源最短路	一个源点 → 所有点	Dijkstra / SPFA / Bellman-Ford	O(m log n) / 视情况 / O(nm)
多源最短路	任意两点之间	Floyd-Warshall	O(n³)
带负权	存在负权边（无负环）	Bellman-Ford / SPFA	不能使用 Dijkstra
存在负环	最短路为 −∞	Bellman-Ford / SPFA 判环	需先判定再回答
边权为 1	无权图	朴素 BFS	O(n + m)
0/1 边权	只有 0 与 1 两种权	0-1 BFS（双端队列）	O(n + m)

🔍 松弛：三种算法共用的那一行代码

设 dis[i] 表示"当前已知的、从源点到 i 的最短距离"。一开始只有 dis[s] = 0，其余全是无穷大（常用 0x3f3f3f3f 或 1e18）。

if (dis[u] + w(u,v) < dis[v]) dis[v] = dis[u] + w(u,v);

直观理解：原来以为"去 v 要绕很远"，现在发现"先到 u，再走一条边就能到 v，还更近"，于是把估计值改小。每松弛一次，dis 数组就单调不增，最多下降有限次，算法必然终止。

收敛判定：当"没有任何一条边还能松弛"时，说明对所有边都满足三角不等式 dis[v] ≤ dis[u] + w，此时 dis 就是真正的最短路（前提：不存在从源点可达的负环）。

为什么最多松弛 n−1 轮？任何一条最短路最多经过 n 个点，也就是最多 n−1 条边。第 1 轮至少能确定"经过 1 条边可达"的点，第 k 轮至少能确定"经过 k 条边可达"的点，所以 n−1 轮足以确定全部。

∞

初始时 dis[1..6] 全为无穷大（只有 dis[s] = 0），随后被一次次"改小"

🔄 一次松弛的完整示范

当前已知：dis[1] = 0、dis[2] = 7、dis[3] = ∞，边 (2, 3) 的权值为 10

dis[1]0

dis[2]7

dis[3]∞ → 17

dis[2] + w(2,3) = 7 + 10 = 17 小于 ∞，所以把 dis[3] 更新为 17

2Bellman-Ford：老实的 n−1 轮扫描能扛负权

C++Bellman-Ford 算法流程

1. dis[所有点] = INF;  dis[s] = 0;
2. 重复 n - 1 轮：
       对 每一条边 (u, v, w) 做一次松弛
       （本轮一次都没更新 → 提前结束，已经收敛）
3. 再做第 n 轮：
       如果还有边能被松弛 → 存在从源点可达的 负环，最短路无定义
4. 输出 dis 数组

🔍 为什么第 n 轮还能更新 = 有负环？

前面已经论证：n−1 轮之后所有最短路都应确定。如果第 n 轮仍能松弛某条边，说明存在一条"经过 n 条边还能更短"的路径 —— 而一条不含重复点的路径最多只有 n−1 条边，所以这条更短的"路径"必然重复经过了某个点，也就是包含一个环。

既然走这个环让距离变小了，这个环的权值之和必然为负。于是"绕着这个环无限转圈"可以让距离无限小，最短路不存在（记作 −∞）。

注意：只有"从源点可达"的负环才会影响答案。如果负环在源点到不了的位置，不会破坏本次的最短路结果（但通常题目会要求判定全局负环）。

👍 优点

可以处理负权边
可以检测负环
代码极短，不易写错
支持"限制最多走 k 条边"的变形（把轮数改成 k）
可以解决差分约束系统

👎 缺点

复杂度 O(nm)，n、m 稍大就超时
大量无用的重复扫描
实现上必须用"边表"存图，不能用邻接表直接遍历
实际竞赛中几乎只用于"判负环"或"差分约束"

C++Bellman-Ford 模板（含负环检测）

const int MAXN = 2005, MAXM = 6005;
const long long INF = 1e18;

struct Edge { int u, v; long long w; } e[MAXM];
long long dis[MAXN];
int n, m, s;

bool bellmanFord() {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;

    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (int i = 1; i <= m; i++) {
            if (dis[e[i].u] == INF) continue;               // 源点还到不了 u
            if (dis[e[i].u] + e[i].w < dis[e[i].v]) {
                dis[e[i].v] = dis[e[i].u] + e[i].w;
                changed = true;
            }
        }
        if (!changed) break;                          // 提前收敛
    }

    // 第 n 轮：还能松弛说明有负环
    for (int i = 1; i <= m; i++)
        if (dis[e[i].u] != INF && dis[e[i].u] + e[i].w < dis[e[i].v])
            return false;                              // 存在负环

    return true;                                      // 无负环，dis 即答案
}

复杂度 O(nm)。n = 2000、m = 6000 时约 1.2×10⁷ 次运算，可以接受；n、m 上万就务必换算法。

3SPFA：队列优化的 Bellman-Ford 平均很快

Bellman-Ford 每一轮都要把 m 条边全扫一遍，但真正"有变化"的往往只有少数几个点。SPFA 的想法就是：只把刚刚被改小过的点放进队列，用它们去松弛邻居。

🔍 算法流程

第1步：dis 数组初始化（源点为 0，其余无穷），vis[i] 表示 i 是否在队列里，源点入队。

第2步：取出队头 u，vis[u] = false，遍历 u 的所有出边：若 dis[u] + w < dis[v] 就更新 dis[v]；若 v 不在队列中，把 v 入队并标记。

第3步：重复直到队列为空。此时 dis 即为答案（无负环时）。

负环判定：记录 cnt[v] = v 的入队次数。若某个点的入队次数达到 n 次，说明它被反复"改小"了至少 n 次，必然存在负环。（另一种写法是记录"最短路的边数"，超过 n−1 也说明有负环。）

复杂度：平均约 O(km)（k 是小常数，通常 2~3），但最坏可达 O(nm)。因此 SPFA 在题目刻意构造的"网格图 + 卡 SPFA"数据下会超时 —— 这是竞赛圈"SPFA 已死"的说法来源。

① 初始化源点入队

② 取队头出队并清标记

③ 松弛邻居变小就入队

④ 结束 / 判环队列空或入队 n 次

C++SPFA 模板（vector 邻接表 + 负环检测）

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

const int MAXN = 20005;
const long long INF = 1e18;

struct To { int v; long long w; };
vector<To> g[MAXN];
long long dis[MAXN];
int cnt[MAXN];              // 每个点的入队次数
bool inq[MAXN];              // 是否在队列中
int n, m, s;

bool spfa() {
    for (int i = 1; i <= n; i++) { dis[i] = INF; inq[i] = false; cnt[i] = 0; }
    dis[s] = 0;

    queue<int> q;
    q.push(s); inq[s] = true; cnt[s] = 1;

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

        for (auto& ed : g[u]) {
            if (dis[u] + ed.w < dis[ed.v]) {
                dis[ed.v] = dis[u] + ed.w;
                if (!inq[ed.v]) {
                    q.push(ed.v);
                    inq[ed.v] = true;
                    if (++cnt[ed.v] >= n) return false;   // 入队 n 次 → 负环
                }
            }
        }
    }
    return true;
}

✅ SPFA 的适用场景

有负权边的图、需要判负环、差分约束系统。只要题目保证"不卡 SPFA"，它就是最好写的负权最短路。

❌ 不要盲目用 SPFA

边权全为非负时，堆优化 Dijkstra 复杂度严格 O(m log n) 且稳定。用 SPFA 反而可能被构造数据（如网格图）卡到 O(nm) 超时。

4Dijkstra：借非负权把堆顶一次定型首选

🔍 贪心策略与它的正确性前提

做法：维护"未确定最短路"的点集。每轮从其中取出 dis 最小的点 u，宣布 dis[u] 已经是最短距离、不再修改，然后用 u 去松弛它的所有出边。重复 n 次。

正确性（非负权是关键）：设当前 dis 最小的未确定点是 u。假设 u 真正的最短路还要经过另一个未确定的点 v，那么这条路径的长度至少是 dis[v]（因为路径从源点到 v 的那一段已经不短于 dis[v]），而 dis[v] ≥ dis[u]（u 是当前最小）；再加上从 v 到 u 的非负那一段，总长度必然 ≥ dis[u]。所以没有更短的路径，dis[u] 可以定稿。

为什么边权必须非负？如果存在负权边，那么"dis[v] 大 + 后面接一条负权边"完全可能比 dis[u] 还小。此时"当前最小者"就不能定稿了，贪心失效。

实测反例：三角形，边 1-2(1)、1-3(5)、2-3(−10)。Dijkstra 会先定稿 dis[3] = 5，但真实最短是 1→2→3 = −9，答案错误。

▶ Dijkstra 逐点定稿过程（6 点示例）

0初始：dis[1] = 0，其余全为 ∞。待定集合 = {1,2,3,4,5,6}。

1弹出 dis 最小的 1 号点（0），定稿。松弛出边：dis[2] = 7、dis[3] = 9、dis[6] = 14。

2待定中最小的是 2 号点（7），定稿。松弛：2-3 权 10 → 7+10 = 17 大于 9，不改；2-4 权 15 → 22，dis[4] = 22。

3最小是 3 号点（9），定稿。松弛：3-4 权 11 → 9+11 = 20 < 22，dis[4] 改小为 20；3-6 权 2 → 11 < 14，dis[6] 改小为 11。

4最小是 6 号点（11），定稿。松弛：6-5 权 9 → 11+9 = 20，dis[5] = 20。

5最小是 4 号点（20），定稿。松弛：4-5 权 6 → 26 大于 20，不改。最后弹出 5 号点（20）定稿，全部完成。

6最终答案：dis = [0, 7, 9, 20, 20, 11]。注意 4 号点被改小过一次（22 → 20），这正是"先入堆、后更新"的典型现象。

要点：弹出即定稿，但同一个点可能被多次入堆，所以堆优化版必须加"过期跳过"的判断。

C++Dijkstra 朴素版 · O(n²)（邻接矩阵）

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n, m, s;
int g[MAXN][MAXN], dis[MAXN];
bool vis[MAXN];

void dijkstra() {
    for (int i = 1; i <= n; i++) { dis[i] = INF; vis[i] = false; }
    dis[s] = 0;

    for (int round = 1; round <= n; round++) {
        int u = 0;
        for (int i = 1; i <= n; i++)                 // 找未确定点中 dis 最小的
            if (!vis[i] && (u == 0 || dis[i] < dis[u])) u = i;
        if (u == 0 || dis[u] == INF) break;          // 剩下的点都不可达

        vis[u] = true;                              // 定稿
        for (int v = 1; v <= n; v++)               // 用 u 松弛所有邻居
            if (!vis[v] && g[u][v] != INF && dis[u] + g[u][v] < dis[v])
                dis[v] = dis[u] + g[u][v];
    }
}

C++Dijkstra 堆优化版 · O(m log n)（链式前向星）

const int MAXN = 100005, MAXM = 200005;
const long long INF = 1e18;

struct Edge { int to, nxt; long long w; } e[MAXM];
int head[MAXN], cntE = 0;
void add(int u, int v, long long w) {
    e[++cntE] = {v, head[u], w};
    head[u] = cntE;
}

long long dis[MAXN];
bool done[MAXN];
typedef pair<long long, int> PLI;              // (距离, 点)，距离放前面方便排序

void dijkstra(int n, int s) {
    for (int i = 1; i <= n; i++) { dis[i] = INF; done[i] = false; }
    dis[s] = 0;

    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;    // 小根堆
    pq.push({0, s});

    while (!pq.empty()) {
        PLI cur = pq.top(); pq.pop();
        long long d = cur.first;
        int u = cur.second;

        if (done[u]) continue;                     // 过期状态，已定稿
        done[u] = true;                           // 弹出即定稿

        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                pq.push({dis[v], v});               // 入堆，不标记 done
            }
        }
    }
}

注意：入堆时不要标记 done，否则后续更优的路径就进不来了。堆里允许存在同一个点的多条记录。

5存图方式：链式前向星 vs vector 邻接表基础功

✅ vector 邻接表（推荐给初学者）

写法直观、不易越界，遍历用范围 for。缺点是扩容时可能引发额外拷贝（可用 reserve 缓解），且内存开销略大。

✅ 链式前向星（竞赛标准）

用数组模拟链表，内存紧凑、常数小、遍历快。缺点是要多写几行，并且需要 head[] 初始化。

C++两种存图的对照写法

/* ---------- 写法一：vector 邻接表 ---------- */
struct To { int v; long long w; };
vector<To> g[MAXN];

// 加一条有向边 u → v（权 w）
void addVec(int u, int v, long long w) { g[u].push_back({v, w}); }

// 遍历 u 的所有出边
for (auto& ed : g[u]) { /* ed.v, ed.w */ }

// 无向边：加两次
void addVec2(int u, int v, long long w) { addVec(u, v, w); addVec(v, u, w); }

/* ---------- 写法二：链式前向星 ---------- */
struct Edge { int to, nxt; long long w; } e[MAXM];
int head[MAXN], cntE = 0;      // head 初值为 0，用 1 开始编号

void addEdge(int u, int v, long long w) {
    e[++cntE] = {v, head[u], w};    // 新边的 nxt 指向原来的头
    head[u] = cntE;                 // 更新头指针
}
// 遍历 u 的所有出边
for (int i = head[u]; i; i = e[i].nxt) { /* e[i].to, e[i].w */ }

对比项	vector 邻接表	链式前向星
代码长度	短	略长（约 5 行）
内存	约为 2 倍边数 × 16 字节 + 容器开销	严格 m 条边 × 16 字节左右，最省
遍历速度	快	最快（连续内存）
加边的复杂度	均摊 O(1)，偶有扩容	严格 O(1)
反边（网络流用）	需自己记录下标	天然用 `i^1` 配对
建议	日常练习、图论入门	正式比赛、需要极限常数时

🔑 小提醒

无向图每条边要加两次，所以边数组要开到 2×m（链式前向星用 MAXM×2）！这是最经典的 RE 来源之一。

⚖️三种算法选型对比

算法	时间复杂度	能否负权	能否判负环	适用场景
Bellman-Ford	O(nm)	✅ 能	✅ 能（第 n 轮判）	小图 + 负权、差分约束、限制边数
SPFA	平均 O(km)，最坏 O(nm)	✅ 能	✅ 能（入队 ≥ n 次）	有负权但数据不刻意卡
Dijkstra 朴素	O(n²)	❌ 不能	❌ 不能	稠密图、无负权（n ≤ 1000）
Dijkstra 堆优化	O(m log n)	❌ 不能	❌ 不能	非负权最短路的标准答案
BFS	O(n + m)	—（边权全为 1）	—	无权图

题目条件	选什么	理由
无负权，n ≤ 10⁵、m ≤ 2×10⁵	堆优化 Dijkstra	稳定 O(m log n)，不怕卡
无负权，点少边多（n ≤ 1000，m 接近 n²）	朴素 Dijkstra	O(n²) 比 O(m log n) 常数更小
有负权，需判负环	Bellman-Ford 或 SPFA	Dijkstra 完全不能用
有负权，需要"最多走 k 条边"	Bellman-Ford 扫 k 轮	轮数恰好控制边数
边权只有 0 和 1	0-1 BFS（双端队列）	O(n+m)，比 Dijkstra 更快
要求任意两点间距离	Floyd（下一讲）	小图多询问的标配

案例案例1：P4779 单源最短路径（标准版）· 堆优化 Dijkstra 模板题

题目：给定 n 个点、m 条边的有向带权图（边权非负），求源点 s 到所有点的最短距离。

🔍 详细分析过程

第1步：识别模型 —— 单源最短路，边权非负，n ≤ 10⁵、m ≤ 2×10⁵。这是堆优化 Dijkstra 的教科书场景。

第2步：为什么不用朴素版 —— 朴素 O(n²) = 10¹⁰，必然超时；堆优化 O(m log n) ≈ 2×10⁵×17 ≈ 3.4×10⁶，毫无压力。

第3步：存图 —— 用链式前向星（有向图不需要反向边，边数组开 MAXM 即可）。

第4步：优先队列 —— pair<long long, int> 默认按 first 排序，所以把"距离"放前面，配合 greater 得到小根堆。

第5步：过期状态 —— 同一个点可能被多次入堆（因为可能被多次改小）。弹出时若 done[u] 已为真，直接跳过。

第6步：不可达输出 —— 题目要求不可达的点输出 2³¹−1 = 2147483647。

易错：入堆时不要标记 done；距离要用 long long 防溢出；输出要用 %d 或按题目要求处理。

C++P4779 · 堆优化 Dijkstra 完整代码

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

const int MAXN = 100005, MAXM = 200005;
const long long INF = 1e18;

struct Edge { int to, nxt; long long w; } e[MAXM];
int head[MAXN], cntE = 0;

void add(int u, int v, long long w) {
    e[++cntE] = {v, head[u], w};
    head[u] = cntE;
}

int n, m, s;
long long dis[MAXN];
bool done[MAXN];
typedef pair<long long, int> PLI;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        add(u, v, w);
    }

    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;

    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        PLI cur = pq.top(); pq.pop();
        int u = cur.second;
        if (done[u]) continue;              // 已经定稿，跳过
        done[u] = true;

        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                pq.push({dis[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dis[i] == INF ? 2147483647LL : dis[i]) << " \n"[i == n];
    return 0;
}

运行结果

输入: 4 6 1
      1 2 2
      2 3 2
      2 4 1
      1 3 5
      3 4 3
      1 4 5
输出: 0 2 4 3

（1 到 2 是 2；1 到 3 走 1-2-3 = 4 比 1-3 的 5 更短；
  1 到 4 走 1-2-4 = 3 比 1-4 的 5 更短）

💡 想一想

注意输出语句 cout << ... << " \n"[i == n]; —— 这是一个常用小技巧：" \n" 是一个长度为 2 的字符数组，下标 i == n 为 0 时输出空格、为 1 时输出换行。等价于"除最后一个数外都用空格分隔"。

如果题目要求输出不可达为 2³¹−1，直接写 2147483647；若题目要求输出 −1，改一下即可。先读清输出格式，再动手写。

案例案例2：P3371 单源最短路径（弱化版）· SPFA 完整实现可跑负权

题目：给定 n 个点、m 条边的有向图，边权可能为负数（保证不存在负环），求源点 s 到所有点的最短距离，不可达输出 2³¹−1。

🔍 详细分析过程

第1步：为什么不选 Dijkstra —— 边权可能为负。Dijkstra 的贪心前提是"弹出的点距离已定稿"，负权边会让这个前提崩塌。

第2步：SPFA 的核心思想 —— Bellman-Ford 每一轮都在无脑扫描所有边，但一轮里只有"距离被改小的那些点"才可能引起进一步改动。把这些点塞进队列，就得到了 SPFA（队列优化的 Bellman-Ford）。

第3步：三个数组 —— dis[] 最短路估计值、inq[] 该点当前是否在队列里（防止同一时刻重复入队）、cnt[] 该点累计入队次数（用于判负环）。

第4步：松弛 + 入队 —— 只有当 dis[u]+w < dis[v] 时才更新 dis[v]；若 v 不在队列里，就把它push进去。

第5步：负环判定 —— 一个点的最短路最多被改进 n−1 次；若某点入队次数达到 n，说明它在负环上被无限改进，直接判定有负环。

易错：① inq[u] = false 必须写在出队之后；② 入队次数要在真正 push 时 +1，不是每次被松弛就 +1；③ 负环判定是"≥ n"而不是"> n"。

C++SPFA · 最短路 + 负环判定完整代码

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

const int MAXN = 500005;
const long long INF = 1e18;

struct Edge { int to, nxt; long long w; } e[MAXN];
int head[MAXN], cntE = 0;

void add(int u, int v, long long w) {
    e[++cntE] = {v, head[u], w};
    head[u] = cntE;
}

int n, m, s;
long long dis[MAXN];
int cnt[MAXN];          // cnt[i]：i 累计入队次数（判负环用）
bool inq[MAXN];          // inq[i]：i 当前是否在队列中

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        add(u, v, w);
    }

    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;

    queue<int> q;
    q.push(s); inq[s] = true; cnt[s] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;                     // 出队

        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[u] + e[i].w < dis[v]) {    // 能松弛
                dis[v] = dis[u] + e[i].w;
                if (!inq[v]) {                  // 不在队列才入队
                    q.push(v); inq[v] = true;
                    if (++cnt[v] >= n) {        // 入队 n 次 → 负环
                        cout << "有负环" << endl;
                        return 0;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dis[i] == INF ? 2147483647LL : dis[i]) << " \n"[i == n];
    return 0;
}

运行结果（样例1：无负环）

输入: 4 5 1
      1 2 1
      1 3 4
      2 3 2
      2 4 6
      3 4 3
输出: 0 1 3 6

（1→3 走 1-2-3 = 1+2 = 3，比直连的 4 更短；1→4 走 1-2-3-4 = 3+3 = 6）

运行结果（样例2：含负环）

输入: 3 3 1
      1 2 1
      2 3 -2
      3 1 -3
输出: 有负环

（1→2→3→1 一圈净减 −4，可以无限绕圈让距离越来越小）

💡 SPFA 的复杂度是"平均 O(km)，最坏 O(nm)"。出题人可以构造"网格图"把 SPFA 卡到 O(nm)，所以无负权时请老老实实用堆优化 Dijkstra，不要因为有负权模板就无脑 SPFA。

案例案例3：P3385【模板】负环 · 逐轮松弛看清判定原理高频考点

题目：给定一张有向图，判断从 1 号点出发能否到达一个负权环。

🔍 详细分析过程

第1步：负环为什么让最短路无意义 —— 只要从源点能走到负环上，就可以在环里绕任意多圈，每绕一圈距离都变小，于是"最短距离"可以趋近 −∞，不存在最小值。

第2步：n−1 轮的正确性 —— 若图中没有负环，任何一条最短路最多含 n−1 条边，所以扫描 n−1 轮之后 dis 必然收敛（后续再扫不会改变任何值）。

第3步：多扫一轮做检测 —— 在 n−1 轮之后再扫一轮，如果还能把某个 dis 改小，说明存在一条含 ≥ n 条边且更短的路径。一条 n 个点的路径含 ≥ n 条边，必然重复经过某个点，重复的这段就是一个负环。

第4步：只判"源点可达"的负环 —— 题目要求"从 1 号点出发能到达"。所以只需要关心 dis 能被更新的边（dis[u] != INF）。

实现选择：P3385 中 SPFA 更常用（平均更快），但下面同时给出 Bellman-Ford 版本帮助理解原理。

样例	边集	第 1 轮后 dis[1..3]	第 2 轮后 dis[1..3]	结论
无负环	1→2 (3)、2→3 (−2)、1→3 (5)	0, 3, 1	0, 3, 1（不变）	✅ 无负环
有负环	1→2 (1)、2→3 (−2)、3→1 (−3)	−4, 1, −1	−8, −3, −5（还在变小）	❌ 有负环

C++Bellman-Ford 判负环 · 逐轮扫描版

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

const int MAXN = 2005, MAXM = 6005;
const long long INF = 1e18;

struct E { int u, v; long long w; } e[MAXM];
int n, m;
long long dis[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            cin >> e[i].u >> e[i].v >> e[i].w;

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

        bool hasNegCycle = false;
        for (int round = 1; round <= n; round++) {   // 多跑一轮 = n 轮
            bool changed = false;
            for (int i = 1; i <= m; i++) {
                int u = e[i].u, v = e[i].v;
                if (dis[u] != INF && dis[u] + e[i].w < dis[v]) {
                    dis[v] = dis[u] + e[i].w;
                    changed = true;
                }
            }
            if (round == n && changed) {      // 第 n 轮还能改 → 负环
                hasNegCycle = true;
                break;
            }
            if (!changed) break;              // 提前收敛，剪枝
        }

        cout << (hasNegCycle ? "YES" : "NO") << endl;
    }
    return 0;
}

运行结果

输入: 2
      3 3
      1 2 3
      2 3 -2
      1 3 5
      3 3
      1 2 1
      2 3 -2
      3 1 -3
输出: NO
      YES

（第一组扫到第 2 轮就不变了 → NO；第二组第 3 轮还在改 → YES）

💡 想一想

为什么是"第 n 轮还能改"而不是"第 n−1 轮"？因为 n−1 轮是正常求得最短路的轮数，此时不该再有改动；如果第 n 轮还有改动，就说明存在含 n 条边的更短路径 —— 而 n 个点走 n 条边必重复点，重复段即负环。

另外注意 dis[u] != INF && ... 这个条件不能省！如果省略，一边是 INF 的加法可能溢出成负数，把"源点不可达的负环"也误判进来。

模块 03

实践应用

三道递进练习：先用 Dijkstra 打基础，再用 SPFA 处理负权，最后加一层"计数"进阶。

A1基础应用题

求单源最短路并输出整个 dis 数组

给定 5 个点、7 条无向边的带权图（边权均为正），以 1 号点为源点，输出 dis[1..5]：

边集

1-2 权 4；1-3 权 1；2-3 权 2；2-4 权 5；3-4 权 8；4-5 权 3；2-5 权 10

提示：想一想从 1 到 3、到 2、到 4、到 5 各自怎么走最短，再和 Dijkstra 的运行结果对照。

查看参考答案

答案：

dis[1..5] = 0 3 1 8 11

推导：

① dis[1] = 0，dis[3] = 1（直连）。

② dis[2]：直连是 4，走 1-3-2 = 1+2 = 3 → 3。

③ dis[4]：直连 1-3-4 = 1+8 = 9，走 1-3-2-4 = 3+5 = 8 → 8；另外 1-2-4 = 4+5 = 9，也不如 8。

④ dis[5]：1-3-2-4-5 = 3+5+3 = 11 → 11；1-2-5 = 4+10 = 14 更差。

✅ 这道题必须用 Dijkstra 或 SPFA，不能只做一次"逐边扫描"—— 注意 dis[2] 是在 dis[3] 定稿之后才被改小的，这正是"多轮松弛"的意义。

B1进阶应用题

判断图中是否存在从 1 出发可达的负环

给出以下两组数据，分别判断是否有负环：

组 1

n = 3，边：1→2 权 3；2→3 权 −2；1→3 权 5

组 2

n = 3，边：1→2 权 1；2→3 权 −2；3→1 权 −3

提示：手动做两轮松弛，看第二轮 dis 是否还在变化。

查看参考答案

组 1：无负环（NO）

第 1 轮：dis = [0, 3, 1]（1→2 得 3；2→3 得 3−2 = 1，比直连 5 更优）

第 2 轮：dis = [0, 3, 1]，没有任何改动 → 已收敛，无负环。

组 2：有负环（YES）

第 1 轮：dis[2] = 1，dis[3] = 1−2 = −1，dis[1] = −1−3 = −4 → [−4, 1, −1]

第 2 轮：dis[2] = −4+1 = −3，dis[3] = −3−2 = −5，dis[1] = −5−3 = −8 → [−8, −3, −5]

n = 3，第 n = 3 轮仍在变小 → 存在负环。

💡 关键判据：n−1 轮之后再扫一轮，还能更新 → 有负环。而且注意组 2 中源点自己（dis[1]）也被改小了，这正是"负环包含源点"的典型表现。

C1综合应用题

最短路计数：从 1 到各点的最短路径条数

有向图，4 个点、5 条边，边权均为 1：1→2、1→3、2→3、2→4、3→4。以 1 为源点，输出 dis[1..4] 以及到达每个点的最短路条数（答案对 100003 取模，本题数值小可直接输出）。

提示：在松弛时区分两种情况 —— "发现更短路" 和 "发现等长路"。

查看参考答案

答案：

dis = 0 1 1 2

最短路条数 way = 1 1 1 2

推导：设 way[i] 表示从 1 到 i 的最短路条数，way[1] = 1。

① 处理 1：dis[2] = 1、way[2] = way[1] = 1；dis[3] = 1、way[3] = way[1] = 1。

② 处理 2：边 2→3，dis[2]+1 = 2 > dis[3] = 1，不是更短也不是等长 → 忽略；边 2→4，dis[4] = 2、way[4] = way[2] = 1。

③ 处理 3：边 3→4，dis[3]+1 = 2 等于 dis[4] = 2 → way[4] += way[3] = 1+1 = 2。

所以 1 到 4 有两条长度同为 2 的最短路：1-2-4 和 1-3-4。

✨ 核心代码只有三行：
if (d+w < dis[v]) { dis[v]=d+w; way[v]=way[u]; push; }
else if (d+w == dis[v]) { way[v]=(way[v]+way[u])%MOD; }
注意：等长时只累加条数，不重新入队（dis 没变，不需要再松弛出去）。

模块 04

总结提升

①核心要点与万能模板

考点	关键结论	必须记住的细节
松弛操作	if (dis[u]+w < dis[v]) dis[v] = dis[u]+w;	三种算法共用，一切最短路的起点
Bellman-Ford	O(nm)，扫 n−1 轮	第 n 轮还能改 → 有负环；天然支持"限边数 k"
SPFA	平均 O(km)，最坏 O(nm)	只有被改小的点入队；入队 ≥ n 次 → 有负环
Dijkstra（朴素）	O(n²)	稠密图优势；靠 `vis[]` 定稿
Dijkstra（堆优化）	O(m log n)	非负权首选；弹出时用 `done[]` 跳过过期状态
Dijkstra 前提	边权必须非负	负权会破坏"弹出即定稿"的贪心性质
不可达处理	dis 保持 INF	输出时按题目要求转成 2147483647 或 −1
数据溢出	距离用 `long long`	INF 取 `1e18`，别用 INT_MAX（相加会爆）

C++万能模板：堆优化 Dijkstra（非负权标配）

const int MAXN = 100005, MAXM = 200005;
const long long INF = 1e18;
struct Edge { int to, nxt; long long w; } e[MAXM];
int head[MAXN], cntE;
long long dis[MAXN];
bool done[MAXN];
typedef pair<long long, int> PLI;

void add(int u, int v, long long w) { e[++cntE] = {v, head[u], w}; head[u] = cntE; }

void dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) { dis[i] = INF; done[i] = false; }
    dis[s] = 0;
    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        PLI cur = pq.top(); pq.pop();
        int u = cur.second;
        if (done[u]) continue;
        done[u] = true;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                pq.push({dis[v], v});
            }
        }
    }
}

C++万能模板：SPFA（有负权 / 判负环）

bool inq[MAXN];
int cnt[MAXN];               // 入队次数

bool spfa(int s, int n) {     // 返回 true 表示有负环
    for (int i = 1; i <= n; i++) { dis[i] = INF; inq[i] = false; cnt[i] = 0; }
    dis[s] = 0;
    queue<int> q; q.push(s); inq[s] = true; cnt[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v); inq[v] = true;
                    if (++cnt[v] >= n) return true;
                }
            }
        }
    }
    return false;
}

🎯 选型速判

无负权 → 堆优化 Dijkstra；有负权不判环 → SPFA；有负权 + 必须稳 → Bellman-Ford；限边数 k → Bellman-Ford 扫 k 轮；任意两点 → Floyd。

②拓展案例

拓展1差分约束系统：把不等式变成最短路提高组高频

问题：求一组 x₁..xₙ，满足若干形如 x_j − x_i ≤ w 的不等式（也可能形如 ≥、=）。

🔍 转化思路

关键变形：x_j − x_i ≤ w ⟺ x_j ≤ x_i + w —— 这正好就是最短路里的三角不等式形式 dis[v] ≤ dis[u] + w！

建图：对每条约束 x_j − x_i ≤ w，连一条有向边 i → j，权为 w。

求解：新建虚拟源点 0，向所有点连一条权为 0 的边，从 0 跑 SPFA。得到的 dis[1..n] 就是一组可行解。

无解判定：若图中存在负环 → 约束矛盾（例如推出 x₁ ≤ x₁ − 5）→ 输出"无解"。

常见变形：x_j − x_i ≥ w 先乘 −1 变成 x_i − x_j ≤ −w，即连边 j → i 权 −w；x_i = x_j 拆成两条 ≤ 约束。

为什么是"≤"配最短路：最短路求的是满足所有三角不等式的最大值解（"上界最紧"的那组解）；若想求下界最紧，就转成"≥ 配最长路"。

📐 差分约束 = 不等式 → 有向边 → 负环判无解

拓展2分层图最短路：状态多一维，"免费 k 次"不再是难题建模技巧

问题：n 个点 m 条边的带权图，你有 k 次机会把某条边的权看作 0，求 s 到 t 的最小花费。

🔍 建模思路

直观想法：把"用了 j 次免费机会"也当作状态的一部分，得到 (点 u, 已用次数 j) 共 n×(k+1) 个状态。

两种转移：

① 正常走：(u, j) → (v, j)，权 w；

② 用一次机会：(u, j) → (v, j+1)，权 0（j < k 时才允许）。

实现：把二维状态压成一维编号 u + j×n，在这个新图上跑 Dijkstra，状态数 ≤ n(k+1)，边数 ≤ 2m(k+1)，复杂度 O(mk log(nk))。k 一般 ≤ 10，完全可行。

答案：min over j of dis[t + j×n]。

同类变形："最多走 k 条边的最短路"（按边数分层）、"经过的城市数不超过 K"、"油量 / 血量有限"。只要问题里出现"最多/至少用 k 次某操作"，就想想分层图。

🧱 分层图 = 把"用了几次机会"也当作点

拓展3最短路计数与最短路 DAG DAG + DP

问题：统计从 s 到 t 的最短路径条数（mod 100003）。

🔍 两种做法对比

做法一（松弛时计数，O(m log n)）：在 Dijkstra 或 SPFA 的松弛语句里加分支 —— 更短就"覆盖" way[v] = way[u]，等长就"累加" way[v] += way[u]。注意等长时不要重新入队。

做法二（建最短路 DAG，O(m)）：先跑一遍 Dijkstra 得到 dis[]，然后只保留满足 dis[u] + w == dis[v] 的边。所有点按 dis 从小到大排好序，这些边一定从 dis 小指向 dis 大（因为 w ≥ 0），于是构成一张 DAG。

在 DAG 上按拓扑序做 DP：way[s] = 1，way[v] = Σ way[u]（对所有保留边 u→v）。

为什么做法二要求非负权：若存在 0 权边，最短路 DAG 上会出现"同层"的边，但仍是 DAG（不会成环，因为 W 恒为正时才有严格递增；w = 0 时同 dis 的点之间可能有环 —— 所以一般题目保证正权）。

推广：同一张最短路 DAG 上还能求"必经过某点的最短路条数"、"最长最短路"、"字典序最小最短路"，是提高组非常常见的组合考点。

🕸️ 最短路 DAG = 最短路的骨架，DP 的舞台

③思考与启发

❌ 错误

① dis[] 用 int，但答案可能超过 2×10⁹；
② INF 取 INT_MAX，做 dis[u] + w 时直接溢出成负数，被误判为"可以松弛"。

✅ 正确

距离一律用 long long，INF 取 1e18（约为 10¹⁸，加到任何 w 都不会溢出 long long 的 9.2×10¹⁸）；
或者用 if (dis[u] != INF && dis[u]+w < dis[v]) 显式保护。

口诀：距离 long long，INF 一 e18；相加之前先想想会不会爆！

📋速查表

算法	复杂度	负权	负环检测	一句话记忆
BFS	O(n + m)	—	—	边权为 1 专用
Dijkstra 朴素	O(n²)	❌	❌	稠密图、每次找最小 dis
Dijkstra 堆优化	O(m log n)	❌	❌	非负权标准答案
Bellman-Ford	O(nm)	✅	✅ 第 n 轮还能改	扫 n−1 轮，可限边数
SPFA	平均 O(km) / 最坏 O(nm)	✅	✅ 入队 ≥ n 次	队列优化的 BF，可能被卡
Floyd	O(n³)	✅	✅ dis[i][i] < 0	任意两点，下一讲

代码动作	标准写法	注意
初始化	for (i=1;i<=n;i++) dis[i]=INF; dis[s]=0;	INF 用 1e18，dis 用 long long
核心松弛	if (dis[u]+w < dis[v]) dis[v] = dis[u]+w;	三算法通用
Dijkstra 定稿	if (done[u]) continue; done[u]=true;	弹出时标记，入堆不标记
SPFA 入队	if (!inq[v]) { q.push(v); inq[v]=true; if(++cnt[v]>=n) 有负环; }	出队要 `inq[u]=false`
BF 判负环	for (round=1; round<=n; round++) { ... if (round==n && changed) 有负环; }	必须加 `dis[u]!=INF`
输出不可达	cout << (dis[i]==INF ? 2147483647LL : dis[i]);	按题目要求改 −1 / 2147483647

📌笔记卡

🧠 必记概念

松弛：dis[v] = min(dis[v], dis[u]+w)
三角不等式：收敛后 dis[v] ≤ dis[u]+w 恒成立
最短路最多 n−1 条边 → BF 扫 n−1 轮
Dijkstra 前提：边权非负
SPFA = 只把"被改小的点"重新入队
负环判定：BF 看第 n 轮 / SPFA 看入队 ≥ n 次

📐 必背模板

堆优化 Dijkstra：priority_queue<PLI, vector<PLI>, greater<PLI>>
链式前向星：e[++cntE]={v,head[u],w}; head[u]=cntE;
SPFA 三数组：dis[]、inq[]、cnt[]
Bellman-Ford：外层 n 轮，内层扫全部边
0-1 BFS：边权 0 入队首、边权 1 入队尾

⚠️ 考场提醒

读题第一件事：看边权是否非负、图有向还是无向
数组大小：无向图边数 ×2，链式前向星 MAXM×2
INF 别用 INT_MAX，用 1e18 + long long
多组数据要清空 head[]、cntE=0、cnt[]
SPFA 有被卡风险，非负权一律 Dijkstra
输出格式（空格/换行/不可达值）先对样例

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础（4题）

A1概念题

单源最短路、松弛操作、负环分别是什么？为什么 Dijkstra 不能处理负权边？

查看参考答案

单源最短路：给定源点 s，求 s 到图中所有点的最短路径长度。当图中不存在从 s 可达的负环时，这个长度一定存在且有限。

松弛：核心操作 if (dis[u]+w < dis[v]) dis[v] = dis[u]+w;。每次松弛都让 dis 单调不增；当所有边都满足三角不等式 dis[v] ≤ dis[u]+w 时收敛，此时 dis 即为最短路。

负环：环上边权之和为负数的环。若从源点可达，则可在环上无限绕行让距离趋于 −∞，"最短路"不存在。Bellman-Ford 用"第 n 轮还能更新"判定，SPFA 用"入队次数 ≥ n"判定。

Dijkstra 为什么怕负权：它每次从堆中弹出当前 dis 最小的点并宣布"定稿"，前提是"之后不可能再有更短的路径"。负权边恰好打破这个前提 —— 一条后发现的路径可能更短。反例：1→2(1)、1→3(2)、3→2(−2)、2→4(1)，Dijkstra 得 dis[4]=2，正确答案是 1。

易错：把"不能有负权边"和"不能有负环"混为一谈。Bellman-Ford / SPFA 允许负权边，只禁止（源点可达的）负环。

A2编程题

用 Dijkstra 求下面有向图的单源最短路：4 个点，源点 1，边为 1→2:4、1→3:2、2→3:1、2→4:5、3→4:10。输出 dis[1..4]。

查看参考答案

手算过程：

① 弹出 1(0)：dis[2] = 4、dis[3] = 2。

② 堆中最小是 3(2)，弹出 3：松弛 3→4 得 dis[4] = 12。

③ 弹出 2(4)：松弛 2→3，4+1 = 5 > dis[3] = 2，跳过；松弛 2→4，4+5 = 9 < 12 → dis[4] = 9。

④ 弹出 4(9)：无出边。

答案：dis[1..4] = 0 4 2 9

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct Edge { int to, nxt; long long w; } e[15];
int head[10], cntE;
long long dis[10];
bool done[10];
typedef pair<long long,int> PLI;
void add(int u,int v,long long w){ e[++cntE]={v,head[u],w}; head[u]=cntE; }
int main(){
    int n=4;
    add(1,2,4); add(1,3,2); add(2,3,1);
    add(2,4,5); add(3,4,10);
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    priority_queue<PLI,vector<PLI>,greater<PLI>> pq;
    pq.push({0,1});
    while(!pq.empty()){
        PLI cur=pq.top(); pq.pop();
        int u=cur.second;
        if(done[u]) continue;
        done[u]=true;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v]){ dis[v]=dis[u]+e[i].w; pq.push({dis[v],v}); }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

输出：0 4 2 9

A3判断题

判断下面说法的正误，并说明理由：
（1）SPFA 一定比 Bellman-Ford 快；
（2）有负权边就一定有负环；
（3）Dijkstra 堆优化的复杂度是 O(m log n)，其中 n 是点数；
（4）用 0x3f3f3f3f 作为 INF，可以安全地写 `dis[u] + w < dis[v]`。

查看参考答案

（1）错。SPFA 的平均复杂度 O(km) 更好，但最坏仍是 O(nm)，出题人可以构造数据（网格图等）把 SPFA 卡死。所以"一定更快"不成立，只能说"平均更快"。

（2）错。负权边和负环是两回事。例如只有一条边 1→2 权 −5，图中没有任何环，却有权值为负的边。只有"环上边权之和为负"才叫负环。

（3）对。堆优化 Dijkstra 的复杂度为 O(m log n)，每条边最多引起一次入堆，堆操作 O(log n)。

（4）对（有限度）。0x3f3f3f3f = 1061109567，两倍约 2.12×10⁹，仍然小于 int 上限 2147483647，所以 INF + w 不会溢出（只要 w 不超过约 10⁹）。这也是为什么竞赛里常写 memset(dis, 0x3f, sizeof dis)。但若 w 很大或需要累加多次，请改用 long long + 1e18。

易错：直接用 INT_MAX 做 INF 是危险的 —— INT_MAX + 1 会溢出成负数，被误判为"可以松弛"。

A4编程题

用 SPFA 判断下面有向图是否存在从 1 出发可达的负环：n = 4，边为 1→2:1、2→3:2、3→4:−5、4→2:1。

查看参考答案

分析：环 2→3→4→2 的权值和 = 2 + (−5) + 1 = −2 < 0，是负环；而 1→2 可达，所以答案是有负环（YES）。

换句话说：从 1 走到 2 之后，可以沿 2→3→4→2 无限绕圈，每圈让距离减 2，dis[2] 趋向 −∞。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005; const long long INF=1e18;
struct Edge{ int to,nxt; long long w; } e[MAXN];
int head[MAXN],cntE;
void add(int u,int v,long long w){ e[++cntE]={v,head[u],w}; head[u]=cntE; }
int n=4;
long long dis[MAXN];
int cnt[MAXN];
bool inq[MAXN];
int main(){
    add(1,2,1); add(2,3,2);
    add(3,4,-5); add(4,2,1);
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    queue<int> q; q.push(1); inq[1]=true; cnt[1]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); inq[u]=false;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v]){
                dis[v]=dis[u]+e[i].w;
                if(!inq[v]){ q.push(v); inq[v]=true;
                    if(++cnt[v]>=n){ cout<<"YES"; return 0; } }
            }
        }
    }
    cout<<"NO";
    return 0;
}

输出：YES

易错：把 ++cnt[v] 写在 if (!inq[v]) 之外 —— 那样同一轮里被多次改小会重复计数，可能误判。

🟡 B组 · 提高（4题）

B1编程题

最短路 + 路径还原：5 个点，源点 1，有向边 1→2:10、1→4:30、1→5:100、2→3:50、3→5:10、4→3:20、4→5:60。求 dis[1..5] 以及 1 到 5 的具体路径。

查看参考答案

手算：dis[2]=10（1→2）；dis[4]=30（1→4）；dis[3]=min(10+50, 30+20) = 50（走 1→4→3）；dis[5]=min(100, 50+10, 30+60) = 60（走 1→4→3→5）。

答案：dis[1..5] = 0 10 50 30 60；路径：1 → 4 → 3 → 5，长度 60。

做法一（记前驱）：在松弛成功时加一句 pre[v] = u;，最后从 t 沿 pre 回溯到 s，再反向输出。

// 松弛处加一行：
if (dis[u] + e[i].w < dis[v]) {
    dis[v] = dis[u] + e[i].w;
    pre[v] = u;                 // 记录前驱
    pq.push({dis[v], v});
}

// 输出路径（从 t 回溯到 s，再反转）
vector<int> path;
for (int x = t; x; x = pre[x]) path.push_back(x);
reverse(path.begin(), path.end());
for (int x : path) cout << x << " ";

易错：① pre[] 初值要给 0（表示无前驱），回溯时用 while (x) 终止；② 若源点编号不是 1，回溯终止条件要改；③ Dijkstra 记录的前驱一定构成一条合法最短路（因为松弛是"最终确定"的），SPFA 也同样可行。

B2编程题

最短路计数：给定有向图，4 个点、5 条边（权均为 1）：1→2、1→3、2→3、2→4、3→4。求从 1 到每个点的最短距离和最短路径条数（mod 100003）。

查看参考答案

答案：dis = 0 1 1 2；way = 1 1 1 2

从 1 到 4 有两条长度同为 2 的最短路：1-2-4 和 1-3-4。

while (!pq.empty()) {
    PLI cur = pq.top(); pq.pop();
    int u = cur.second;
    if (done[u]) continue;
    done[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        long long nd = dis[u] + e[i].w;
        if (nd < dis[v]) {                 // 发现更短：覆盖条数
            dis[v] = nd;
            way[v] = way[u];
            pq.push({dis[v], v});
        } else if (nd == dis[v]) {         // 发现等长：累加条数
            way[v] = (way[v] + way[u]) % 100003;
        }
    }
}

易错：① 等长时不要再 push 进堆（dis 没变，不需要重新松弛）；② 一定要取模；③ 用 Dijkstra 计数的前提是非负权—— 若有 0 权边，同 dis 的点之间可能互相影响，需要改在最短路 DAG 上按拓扑序 DP。

B3建模题

分层图最短路：4 个点的无向图，边为 1-2:3、2-4:4、1-3:1、3-4:10。你有 1 次机会把某条边的权看作 0，求 1 到 4 的最小花费。

查看参考答案

建模：把状态分成两层：第 0 层 = "还没用机会"，第 1 层 = "已经用了机会"。状态编号取 u + j×n（j = 0,1）。

① 正常走：(u,j) → (v,j)，权 w；② 用机会：(u,0) → (v,1)，权 0。

答案：1

路径：1 → 3（花费 1）→ 4（用掉机会，花费 0），总计 1。若不使用机会，最优是 1-2-4 = 3 + 4 = 7。

// 建图（n 个点、k 次机会，状态总数为 n*(k+1)）
for (int i = 0; i < m; i++) {
    int u = eu[i], v = ev[i]; long long w = ew[i];
    for (int j = 0; j <= k; j++) {
        int a = u + j * n, b = v + j * n;
        add(a, b, w); add(b, a, w);                  // 第 ① 种转移
        if (j < k) {                                 // 第 ② 种转移
            int a2 = u + j * n, b2 = v + (j + 1) * n;
            add(a2, b2, 0); add(b2, a2, 0);
        }
    }
}
// 从 s 跑 Dijkstra，答案是 min over j of dis[t + j*n]

易错：数组要开到 n × (k+1)；边数变为约 2m(k+1)；答案是"所有层里 t 的最小值"，不是只用第 k 层。

B4编程题

邮递员送信：5 个点，有向边（去程与回程权重可能不同）：1→2:5、2→1:3、2→3:4、3→2:2、1→3:10、3→1:1、3→4:6、4→3:7、4→5:2、5→4:1、1→5:9、5→1:4。邮递员从 1 出发给每个点送信并返回 1，求往返总花费。

查看参考答案

关键技巧：去程用原图跑一次 Dijkstra（1 → 各点）；回程（各点 → 1）等价于在 反向图 上从 1 跑一次 Dijkstra。

去程 dis（原图）：0 5 9 10 9 → 各点之和 = 5+9+10+9 = 33

回程 dis（反向图）：0 3 1 6 4 → 各点之和 = 3+1+6+4 = 14

总花费 = 33 + 14 = 47

// 反向图：把每条边 u->v 建成 rev 图上的 v->u
for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    add(u, v, w);              // 原图，算 1 -> i
    addRev(v, u, w);           // 反向图，算 i -> 1
}
dijkstra(1, disF);               // 原图
dijkstraRev(1, disB);           // 反向图
long long ans = 0;
for (int i = 2; i <= n; i++) ans += disF[i] + disB[i];
cout << ans << endl;

为什么反向图有效："i 到 1 的最短路"在反向图上就是"1 到 i 的最短路"（因为把每条边方向反过来，路径也正好反向），这是"多源汇往返"类问题的标准套路。

易错：只跑一次 Dijkstra 然后用 dis[i]×2 当往返 —— 这只有在图是无向时才成立；有向图必须两次。

🔴 C组 · 挑战（4题）

C1建模题

差分约束：求一组整数解 x₁..x₄，满足
x₂ − x₁ ≤ 3；x₃ − x₂ ≤ 2；x₁ − x₃ ≤ −1；x₄ − x₃ ≤ 5；x₁ − x₄ ≤ 4。

查看参考答案

建图规则：把 x_j − x_i ≤ w 变成有向边 i → j 权 w。于是：

1→2 权 3；2→3 权 2；3→1 权 −1；3→4 权 5；4→1 权 4。

再加虚拟源点 0，向 1..4 各连一条权 0 的边（保证所有点都可从源点到达、且不限制上界）。

跑 SPFA 得 dis：dis[1] = 0，dis[2] = 3，dis[3] = 5，dis[4] = 10，并检查无负环 → 存在可行解。

验证：x = (0, 3, 5, 10)：
3−0 = 3 ≤ 3 ✅；5−3 = 2 ≤ 2 ✅；0−5 = −5 ≤ −1 ✅（满足）；10−5 = 5 ≤ 5 ✅；0−10 = −10 ≤ 4 ✅。

int main(){
    int n = 4;
    add(1,2,3); add(2,3,2); add(3,1,-1);
    add(3,4,5); add(4,1,4);
    for (int i = 1; i <= n; i++) add(0, i, 0);   // 虚拟源点
    if (spfa(0, n)) cout << "无解（存在负环）" << endl;
    else for (int i = 1; i <= n; i++) cout << dis[i] << " ";
}

输出：0 3 5 10

易错：① x_j − x_i ≥ w 要先乘 −1 变成 x_i − x_j ≤ −w，即连边 j → i 权 −w，方向别搞反；② 若题目没有给定"存在解"的保证，必须判负环；③ 虚拟源点的边权是 0（因为 x_i ≤ x_0 + 0 只是让 x_0 成为统一上界）。

C2综合题

最短路 DAG + DP：给定一张非负权有向图，求从 1 到 n 的路径中，长度等于最短路的路径条数（mod 10⁹+7），并说出"最短路 DAG"是什么。

查看参考答案

最短路 DAG：先跑一遍 Dijkstra 得到 dis[]，然后只保留满足 dis[u] + w(u,v) == dis[v] 的边。这些边组成的图叫最短路 DAG。因为权非负，这类边一定从 dis 小的点指向 dis 大的点（或相等的 0 权边），所以不含环，是 DAG。

做法一（松弛时计数）：在 Dijkstra 的松弛语句里分支即可，O(m log n)。

做法二（DAG 上 DP）：把点按 dis 从小到大排序（这天然就是一个拓扑序），依次做 way[v] = Σ way[u]（对所有保留边 u→v），way[1] = 1，O(m)。

// 做法二：先 Dijkstra 得到 dis[]，再在 DAG 上按 dis 排序做 DP
sort(id + 1, id + n + 1, [](int a, int b) {
    return dis[a] < dis[b];          // 按 dis 升序 = 拓扑序
});
way[1] = 1;
for (int k = 1; k <= n; k++) {
    int u = id[k];
    if (dis[u] == INF) continue;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (dis[u] + e[i].w != dis[v]) continue;   // 非最短路 DAG 的边，丢弃
        way[v] = (way[v] + way[u]) % 1000000007;
    }
}
cout << way[n] << endl;

两种做法对比：做法一只需一次 Dijkstra，代码最短；做法二多一次排序但仍很轻，而且"最短路 DAG"这个结构本身可以继续承载其他 DP（例如"最长的最短路"、"必经点个数"）。

易错：① 若有 0 权边，同 dis 的点之间可能形成环，排序就不再是有效拓扑序 → 这类题目通常保证边权为正；② 计数别忘了取模；③ 判断"是否在最短路 DAG 上"必须用 ==，不能用 <=。

C3优化题

0-1 BFS：图中边权只有 0 和 1 两种，如何用比 Dijkstra 更快的 O(n+m) 算法求单源最短路？为什么它能这么做？

查看参考答案

核心思想：用双端队列（deque）代替优先队列。

① 取出队首 u，若已定稿则跳过；② 边权为 0 时把 v push_front（因为它和 u 同距离，应该优先处理）；③ 边权为 1 时把 v push_back（因为它比 u 远一层）。

为什么正确：队列中任意时刻的元素，距离值只有两种（d 和 d+1），且队首到队尾单调不减。于是"队首一定是当前全局最小"，这就等价于一个小根堆 —— 只是堆的形态被简化成了双端队列。

deque<int> dq;
for (int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
dq.push_front(s);
while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    if (done[u]) continue;
    done[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to; int w = (int)e[i].w;     // w 只能是 0 或 1
        if (dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            if (w == 0) dq.push_front(v);          // 0 权 → 队首
            else       dq.push_back(v);           // 1 权 → 队尾
        }
    }
}

复杂度对比：Dijkstra 堆优化 O(m log n) vs 0-1 BFS O(n + m)。每个点最多入队 2 次、每条边只被访问一次。

易错：① push_front 之后不能忘记 done[] 的判定，否则 0 权边可能导致同一个点多次扩展；② 边权只能是 0 和 1，若有 2、3 这种权值，就要回到 Dijkstra；③ 记住"0 权前插、1 权后插"，反过来就完全错了。

C4综合题

最小瓶颈路：给定无向带权图，定义一条路径的"代价"为路径上最大的边权。求从 s 到 t 的所有路径中，代价的最小值。请给出两种解法。

查看参考答案

解法一：最小生成树（推荐）——先求整张图的 MST，在 MST 上 s 到 t 的唯一路径就是一个最小瓶颈路，其最大边权即为答案。

为什么正确（kruskal 视角）：Kruskal 按边权从小到大加边，s 与 t 第一次连通时所加的那条边，就是"能让 s、t 连通的最小边权上界"。这条边恰好是 MST 路径上的最大边。

解法二：二分答案 + 并查集/BFS——二分答案 W：只保留边权 ≤ W 的边，检查 s 与 t 是否连通。连通性单调（W 越大越容易连通），可以二分，复杂度 O(m log m + (n+m) log W)。

// 解法一：Kruskal 建 MST，再在 MST 上从 s 出发 DFS 求路径最大边
int find(int x){ while(fa[x]!=x){ fa[x]=fa[fa[x]]; x=fa[x]; } return x; }
sort(e, e + m, [](const E&a, const E&b){ return a.w < b.w; });
int cnt = 0;
for (int i = 0; i < m && cnt < n - 1; i++) {
    int ra = find(e[i].u), rb = find(e[i].v);
    if (ra == rb) continue;
    fa[ra] = rb; cnt++;
    addTree(e[i].u, e[i].v, e[i].w);      // 只加进 MST 的树边
    addTree(e[i].v, e[i].u, e[i].w);
}
// 从 s 开始 DFS，记录沿途边权最大值，走到 t 时的值即为答案

答案（示例）：4 个点、边为 1-2:1、2-3:5、3-4:2、1-3:4、1-4:3，求 1→4 的最小瓶颈路：MST 选 1-2(1)、3-4(2)、1-4(3)，路径 1→4 上是边 1-4 权 3，答案 = 3（直接走 1-4）。

易错：① 最小瓶颈路 ≠ 最短路（最短路优化的是边权和）；② 如果多次询问，建 MST 后用 LCA / 树链剖分求路径最大值，可以把每次询问降到 O(log n)；③ 二分解法要注意 check 的单调性方向。

🔵 洛谷原题精选（12 道）

按难度从易到难排序，建议先做题号 1~6（普及难度）建立手感，再攻 7~12。

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

P1339
[USACO09OCT] Heat Wave G入门

P1529
[USACO2.4] Bessie Come Home G入门

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

P1629
邮递员送信普及

P1576
最小花费普及

P1144
最短路计数普及

P1807
最长路普及

P3385
【模板】负环普及

P5960
【模板】差分约束算法提高

P1608
路径统计提高

P2865
[USACO06NOV] Roadblocks G提高

情景导航

导航的实时重算

广播传消息

只通知有变化的人

按身高排队领奖

知识探究

👍 优点

👎 缺点

✅ SPFA 的适用场景

❌ 不要盲目用 SPFA

✅ vector 邻接表（推荐给初学者）

✅ 链式前向星（竞赛标准）

💡 想一想

💡 想一想

实践应用

求单源最短路并输出整个 dis 数组

判断图中是否存在从 1 出发可达的负环

最短路计数：从 1 到各点的最短路径条数

总结提升

🤔 思考1：为什么 Dijkstra 遇到负权边就"翻车"？

🤔 思考2：SPFA 真的比 Bellman-Ford 好吗？为什么竞赛里有人说"不要写 SPFA"？

🤔 思考3：如果图里有负环，"最短路"还能定义吗？谈谈"无解"与"−∞"的区别

学习检测

Dijkstra 用负权图

堆优化 Dijkstra 在入堆时就标记"已定稿"

SPFA 忘记清空 inq / 入队次数判错

无向图边数组忘记开 2 倍

INF 太小 / 用 int 存距离导致溢出

🧠 必记概念

📐 必背模板

⚠️ 考场提醒

分层练习作业

🟢 A组 · 基础（4题）

单源最短路、松弛操作、负环分别是什么？为什么 Dijkstra 不能处理负权边？

用 Dijkstra 求下面有向图的单源最短路：4 个点，源点 1，边为 1→2:4、1→3:2、2→3:1、2→4:5、3→4:10。输出 dis[1..4]。

判断下面说法的正误，并说明理由：（1）SPFA 一定比 Bellman-Ford 快；（2）有负权边就一定有负环；（3）Dijkstra 堆优化的复杂度是 O(m log n)，其中 n 是点数；（4）用 0x3f3f3f3f 作为 INF，可以安全地写 dis[u] + w < dis[v]。

用 SPFA 判断下面有向图是否存在从 1 出发可达的负环：n = 4，边为 1→2:1、2→3:2、3→4:−5、4→2:1。

🟡 B组 · 提高（4题）

最短路 + 路径还原：5 个点，源点 1，有向边 1→2:10、1→4:30、1→5:100、2→3:50、3→5:10、4→3:20、4→5:60。求 dis[1..5] 以及 1 到 5 的具体路径。

最短路计数：给定有向图，4 个点、5 条边（权均为 1）：1→2、1→3、2→3、2→4、3→4。求从 1 到每个点的最短距离和最短路径条数（mod 100003）。

分层图最短路：4 个点的无向图，边为 1-2:3、2-4:4、1-3:1、3-4:10。你有 1 次机会把某条边的权看作 0，求 1 到 4 的最小花费。

邮递员送信：5 个点，有向边（去程与回程权重可能不同）：1→2:5、2→1:3、2→3:4、3→2:2、1→3:10、3→1:1、3→4:6、4→3:7、4→5:2、5→4:1、1→5:9、5→1:4。邮递员从 1 出发给每个点送信并返回 1，求往返总花费。

🔴 C组 · 挑战（4题）

差分约束：求一组整数解 x₁..x₄，满足x₂ − x₁ ≤ 3；x₃ − x₂ ≤ 2；x₁ − x₃ ≤ −1；x₄ − x₃ ≤ 5；x₁ − x₄ ≤ 4。

最短路 DAG + DP：给定一张非负权有向图，求从 1 到 n 的路径中，长度等于最短路的路径条数（mod 109+7），并说出"最短路 DAG"是什么。

0-1 BFS：图中边权只有 0 和 1 两种，如何用比 Dijkstra 更快的 O(n+m) 算法求单源最短路？为什么它能这么做？

最小瓶颈路：给定无向带权图，定义一条路径的"代价"为路径上最大的边权。求从 s 到 t 的所有路径中，代价的最小值。请给出两种解法。

🔵 洛谷原题精选（12 道）

判断下面说法的正误，并说明理由：
（1）SPFA 一定比 Bellman-Ford 快；
（2）有负权边就一定有负环；
（3）Dijkstra 堆优化的复杂度是 O(m log n)，其中 n 是点数；
（4）用 0x3f3f3f3f 作为 INF，可以安全地写 `dis[u] + w < dis[v]`。

差分约束：求一组整数解 x₁..x₄，满足
x₂ − x₁ ≤ 3；x₃ − x₂ ≤ 2；x₁ − x₃ ≤ −1；x₄ − x₃ ≤ 5；x₁ − x₄ ≤ 4。

最短路 DAG + DP：给定一张非负权有向图，求从 1 到 n 的路径中，长度等于最短路的路径条数（mod 10⁹+7），并说出"最短路 DAG"是什么。