第 31 章结尾我写了这么两句：
① 第 30 章的 BFS 已经能求最短路了，但那是每条边都一样长的情况。 边一带权，「一圈一圈往外扩」就不成立了 —— 走三条短边可能比走一条长边还近。 ② 把第 31 章那个小根堆原样搬过去，就是「堆优化 Dijkstra」。容器换了，套路没变。
第 3 步兑现第一句（拿一张具体的图，把 8 和 9 这两个数摆出来）， 第 6 步兑现第二句（两段代码并排，只有一行不一样）。
而这一章真正的新东西在第 9 步：为什么有负权边就不行。 到那里你会发现，连「不行」这两个字都得说得更小心 —— 不行的不是那份代码，是那句「取出来就定死」。
1 一句话问题
给一张有向图：
n个点、m条边，每条写成u v w， 表示「从 u 到 v 有一条路，长w」（1 ≤ w ≤ 100）。再给一个起点s。求 s 到每个点的最短距离；走不到的输出
-1（s 到自己是 0）。⚠ 可能有重边，也可能有自环；⚠ 也可能有从 s 根本走不到的点。
和第 30、31 章一样，这三句限制不是为了刁难：
- 可能有重边 → 逼你在建图时想清楚「两条 u → v 该留哪条」（第 29 章那条）；
- 可能有自环 → 边长为正时它对答案毫无影响，但代码里必须经得住它；
- 可能有走不到的点 →
-1那一支必须真的被走到。 ⚠ 而这一句最容易在写生成器时被自己偷偷取消（「有一串 -1 的数据看着不像话」）—— 第 12 步那张表里，它值 51 / 300。
⚠ 还有一句没写在题面里、但同样重要的：起点 s 不一定是 1 号。
第 30 章刚刚在这上面栽过一次，这一章又准备了一份 wrongStart1.cpp 专门盯它。
2 手算一遍：7 个点、11 条边，起点是 5 号
7 11 5
5 6 2 ┐
6 7 3 │ 一条链：5 →(2) 6 →(3) 7 →(1) 4 →(2) 1 →(1) 2
7 4 1 │
4 1 2 ┘
5 1 9 ← ★ 一条「抄近路」的长边：5 直接到 1，长 9
1 2 1
7 2 7 ← 另一条通往 2 号的路（5+7 = 12，绕远了）
3 2 4 ← ⚠ 3 号自己有出边，但**没人指向它** → 从 5 号走不到 3 号
2 4 3 ← ⚠ 一条「回指」的边：从远处（9）指回近处（6）
5 6 6 ← ⚠ 重边：5 → 6 已经有一条长 2 的了，这条长 6
4 4 5 ← ⚠ 自环一步一步往外定（每次挑「已知距离里最小、而且还没定下来的那个」）：
| 这一步定死谁 | 它的距离 | 定死之后，谁变近了 |
|---|---|---|
| 5（起点） | 0 | 6 → 2，1 → 9（走那条长边） |
| 6 | 2 | 7 → 5 |
| 7 | 5 | 4 → 6，2 → 12 |
| 4 | 6 | ★ 1 → 8（2+3+1+2，比那条长边的 9 还近！） |
| 1 | 8 | 2 → 9 |
| 2 | 9 | 4 → 9+3 = 12，比 6 大，不动 |
3 号走不到，输出 -1。最终答案：
8 9 -1 6 0 2 5★ 请把第 4 行那个 8 和 9 记住 —— 上一章欠下的那句「走三条短边可能比一条长边还近」， 在这张图上就是这两个数字。整章有一半的内容都挂在它上面。
3 ★ 兑现预告①：把上一章那份 BFS 原样搬来，会错在哪
第 30 章的 BFS 求的是「最少几步」。这道题看着就像它，很多人的第一反应是：
把 dist[v] = dist[u] + 1 改成 dist[v] = dist[u] + w 不就行了？
点「运行 ▶」看结果
跑出 9 10 -1 6 0 2 5 —— 1 号是 9，2 号是 10，都比正解大了 1。
BFS 里有一句几乎没人多看一眼的话：入队时打 vis，每个点只入队一次。
翻译过来是：
谁先被碰到，谁的距离就定死。
在第 30 章那里这是对的，因为每条边都一样长，「先被碰到」就等于「边数最少」， 而边数最少就是最短。可现在 ——
- 5 号一出队，就顺着那条长边碰到了 1 号，
dist[1]当场定成 9； - 等它绕完
6 → 7 → 4走到 1 号时，那条 8 的路已经没人听了。
★ BFS 排的是「边数」，这道题要的是「边长之和」。 两者一致，只在「每条边都一样长」的时候。
⚠ 顺带记一笔：这也说明边权全相等的数据什么都验不出来 —— 那种数据上这份代码是完全正确的。第 12 步那张表的第一行就是这么来的（0 / 300）。
4 标准答案：Floyd —— 一个完全不一样的思路
对拍要的是思路不同的两份代码（第 9 章那条规矩）。这一章挑的是 Floyd：
点「运行 ▶」看结果
| Dijkstra | Floyd | |
|---|---|---|
| 想法 | 每次挑一个点，把它的距离定死 | d[i][j] 只允许拿前 k 个点当中转站，k 从 0 涨到 n |
| 属于 | 贪心 | DP |
| 复杂度 | O(n²) 或 O(m log n) | O(n³) |
一个贪心、一个 DP，不可能一起错。这一章先把它当黑盒用， 第 33 章会讲透它（尤其是「为什么 k 必须在最外层」）。
① d[u][v] = min(d[u][v], w) —— 重边必须取 min。写成直接赋值的话，
默认那张图里那条 5 6 6 会把前面那条 5 6 2 覆盖掉，答案当场错。
② INF 取 0x3f3f3f3f（约 10.6 亿）而不是 INT_MAX。理由就在三重循环那一行：
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);两个 INF 相加是 21.2 亿，还没溢出 int（上限 21.47 亿）。
换成 INT_MAX 的话这一句当场变成负数，「走不到」会被刷成一个负距离、还会顺着边传染。
★ 0x3f3f3f3f 这个惯用法，整个就是为了这一句而存在的。
5 ★ 关键一步：取当前最近的那个，它的距离当场就定死
点「运行 ▶」看结果
整个算法就三句话，一句一行：
int u = -1; // ① 在还没定下来的点里，挑距离最小的
for (int j = 1; j <= n; j++)
if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
vis[u] = 1; // ② ★ 它的距离从此定死
for (auto [v, w] : g[u]) // ③ 拿它去松弛邻居
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;设 u 是此刻 dist 最小的未确定点。假如真有一条更短的 s → u 的路，那么：
- 那条路总要在某处第一次离开「已经定死的那堆点」，设它踏出来踩到的第一个未确定点是 x；
- 于是 那条路的长度 ≥ 走到 x 的那一段 ≥ dist[x] ≥ dist[u] （最后一个 ≥ 是因为 u 是当前最小的）；
- ——「更短」不成立。矛盾。
★ 现在请盯住第一个 ≥：它说的是「从 x 接着走到 u 的那一段 ≥ 0」。
这一步用掉了「边长非负」这个条件，而且全程只用在这一处。
记住这句话。第 9 步会把它拆掉，然后你会看到反例正好长在这个位置上 —— 第 20 章那句「交换论证断在哪一步，反例就长在哪里」，这是它第三次登场。
dist[v] = dist[u] + w 前面那个 if 不是可有可无的检查，它就是「松弛」两个字本身：
如果经过 u 更近，就把 v 的距离「放松」到这个更小的值。
它天生是单向的：只许变小，不许变大。
把那个 if 去掉，就是第 10 步那个 wrongRelax.cpp —— 而它在默认那张图上错得相当难看。
6 ★ 兑现预告②：把第 31 章的小根堆原样搬过来
朴素版慢在第 ① 句：为了找一个最小值，扫了 n 个点。而「不断加进来、每次取最小」—— 这不正是上一章那个小根堆干的活吗？
点「运行 ▶」看结果
// 第 31 章（拓扑排序）
priority_queue<int, vector<int>, greater<int>> q; // 堆里放：编号
q.push(v); // 入堆条件：入度减到 0
// 这一章（Dijkstra）
priority_queue<PII, vector<PII>, greater<PII>> q; // 堆里放：(距离, 编号)
q.push({dist[v], v}); // 入堆条件：距离变小了同一个容器、同一个 greater<>、同一套写法。 变的只有两件事：
| 第 31 章 | 这一章 | |
|---|---|---|
| 堆里放什么 | 编号 | ★ (距离, 编号) |
| 什么时候入堆 | 入度减到 0 | 距离变小了 |
pair 的比较是先比第一维，所以把距离放在前面，堆就按距离排 —— 就这么一件事。
⚠ 只搬容器、忘了改放进去的东西，就是第 10 步那个 wrongHeapId.cpp。
一个点的距离在被定死之前可能被刷小好几次，每次都往堆里塞一份新的 (距离, 编号)。
标准堆没法把旧的那份删掉，所以我们等它出来的时候再看一眼：
它带的距离比现在记录的还大 → 它是过期的 → 直接扔掉。
这一句同时也顶替了朴素版里 vis[] 的角色：一个点真正被处理，只会有一次。
★ 请把这句话记牢，第 9 步会拿它做文章 —— 那时你会发现， 正是这一句，让这份代码在负权图上「不小心」变成了另一个算法。
7 实测：朴素 O(n²) 和堆优化，到底差多少
本机实测（./genBig <n>，边数取 2n，固定种子，只能在终端里跑 ——
十几 MB 的数据传不进网页那个小工具）：
g++ -O2 -std=c++17 -o genBig genBig.cpp && g++ -O2 -std=c++17 -o naive naive.cpp
g++ -O2 -std=c++17 -o fast fast.cpp
./genBig 40000 > big.txt
time ./naive < big.txt > /dev/null # 3.5 秒
time ./fast < big.txt > /dev/null # 0.02 秒| 命令 | 点数 n | 边数 | 朴素 O(n²) | 堆优化 |
|---|---|---|---|---|
./genBig 10000 | 1 万 | 29 999 | 0.16 秒 | 0.00 秒 |
./genBig 20000 | 2 万 | 59 999 | 0.90 秒 | 0.01 秒 |
./genBig 40000 | 4 万 | 119 999 | 3.53 秒 | 0.02 秒 |
./genBig 80000 | 8 万 | 239 999 | 13.56 秒 | 0.05 秒 |
./genBig 160000 | 16 万 | 479 999 | 56.63 秒 | 0.18 秒 |
★ n 翻一倍，朴素慢四倍，堆优化只慢一倍。 16 万个点时差了三百多倍。
常见的说法是：朴素是 O(n²)、对边数完全不敏感，而堆优化是 O(m log n)；
所以 m 接近 n² 的稠密图上，朴素反而更快。
我本来是打算把这张表做出来的。做不出来。
（./genBig <n> <m>，第二个参数就是边数，同样只能在终端跑：）
| 点数 | 边数 | 朴素 | 堆优化 |
|---|---|---|---|
| 3000 | 30 万 | 0.03 秒 | 0.02 秒 |
| 3000 | 100 万 | 0.09 秒 | 0.08 秒 |
| 3000 | 300 万 | 0.27 秒 | 0.26 秒 |
| 3000 | 900 万（≈ n²） | 0.86 秒 | 0.79 秒 |
一直拧到 m ≈ n²，堆优化还是没输过。为什么？count.cpp 一跑就明白了：
点「运行 ▶」看结果
★ 实测的入堆次数（这几个数字都钉在 check:viz 里）：
| 图 | 边数 | 入堆次数 |
|---|---|---|
./genBig 2000 200000 | 20 万 | 8 385 |
./genBig 2000 2000000 | 200 万 | 12 251 |
./genBig 3000 9000000 | 900 万 | 19 847 |
边数翻了十倍，入堆次数只涨了四成。
原因很简单，但很容易被 O(m log n) 这个记号盖住：
一条边只有在「真的把某个点刷小了」的时候才入堆。
随机图上绝大多数边刚看一眼就被 if 挡回去了，m log n 是个非常松的上界。
而朴素版那个 n² 是结结实实的 n²，一次都省不掉。
★ 口诀要拿实测复核，别默认它到处成立。 第 29 章刚在「链式前向星常数最小」上栽过一次（稠密图上它慢四倍），这是第二次。 ⚠ 但也别把我的结论反过来当口诀背：
m log n那个上界是能被吃满的， 只是要专门构造数据。我说的是「随机数据上复现不出来」，不是「它不存在」。
8 动画：一圈一圈地把点定死
点上面的数字是「目前知道的最短距离」（∞ = 还没碰到过），绿色表示已经定死。 右边那个大数字是 ★ 已经定死的点数 —— 正权图上它最多涨到「走得到的点数」， 一个点只定死一次。
下拉框里四个错误版本第 10 步逐个讲。 ★ 现在先切一下前两个（BFS / 堆里放编号）—— 它们在这张图上给出一模一样的错答案。
9 10 -1 6 0 2 5：一个是按边数排的，一个是按编号排的，
可它们的共同点是 ——「没按距离排」。
这也顺带演示了第 20 章那个盲区的另一面： 对拍看到两份程序答案相同，并不等于它们都对。 它们只是错在同一个地方。
9 ★ 为什么有负权边就不行 —— 这一章真正的新东西
回到第 5 步那个证明。它一共用了三个 ≥，而「边长非负」只在第一个里出现过一次：
那条路的长度 ≥ 走到 x 的那一段 ≥ dist[x] ≥ dist[u]
↑
这里用掉了「x 走到 u 的那一段 ≥ 0」把这一处拆掉，反例就该长在这里。四个点就够了：
4 4 1
1 2 3 ← 1 到 2 有一条直达的，长 3
1 3 5 ← 1 到 3 长 5
3 2 -4 ← ★ 3 到 2 是 -4
2 4 1真相：到 2 号最近的是 1 → 3 → 2 = 5 − 4 = 1，于是到 4 号是 2。
可朴素 Dijkstra 一上来就把 2 号定死在 3（因为 3 < 5）——
点「运行 ▶」看结果
跑出 0 1 5 4，而正确答案是 0 1 5 2。
★ 注意 2 号那一位它是对的（1）—— 因为后来那次松弛确实把 dist[2] 改小了。
错的是 4 号：dist[2] 被改小的时候，2 号早已定死出场，
没有人再拿新的 1 去更新它的下游。
|这条路| ≥ |走到 x 的那段| ≥ dist[x] ≥ dist[u]
⚠ 第一个 ≥ 用掉的正是「x 到 u 那一段 ≥ 0」，也就是边长非负 —— 全程只在这一处用到它。所以负权边一来，断的就是这一处。
这个动画每定死一个点，就把「起点到它的所有简单路径」暴力枚举一遍，当场对质。 正权那张图上一次都推不翻；按一下按钮换成负权那张，第 2 步就被推翻， 而且推翻它的那条路上那条负权边会被标红 —— 那就是证明断掉的地方。
现在把同一张负权图喂给堆优化那一份：
点「运行 ▶」看结果
0 1 5 2 —— 它是对的。 而且不是碰巧：genNeg.cpp 造的 300 组负权数据里，
| 和 Floyd 不一致的轮数 | |
|---|---|
| 朴素 O(n²) | 35 / 300（第 3 轮就抓到） |
| 堆优化 | 0 / 300 |
★ 所以「Dijkstra 对负权不成立」这句话，准确的说法是：
不成立的是那句「取出来的一刻，它的距离就定死」。 而堆优化那份代码，早就不遵守这句话了。
回头看第 6 步那句 if (d > dist[u]) continue;：它扔掉的只是过期的记录。
一个点被刷小之后会带着新距离重新入堆、重新被处理 ——
于是它悄悄退化成了「优先队列版的 Bellman-Ford」（第 33 章的内容）。
count.cpp 把这件事量了出来：
点「运行 ▶」看结果
4 个点，却被真正处理了 6 次。 一个点被处理不止一次， 「定死」这两个字在这张图上就已经不成立了。
⚠ 而且它换来的正确答案是有代价的：最坏情况下入堆次数可以爆炸，
碰上负环更是根本停不下来（count.cpp 里那个 POP_LIMIT 就是为此准备的刹车）。
负权的正经办法在第 33 章：Bellman-Ford / SPFA，外加判负环。
这一节有个绕不过去的技术问题：有负环的话最短路根本不存在 （绕着环走一圈更短，可以无限短），Floyd 也给不出答案，那就什么都验不了。
办法叫势函数（第 33 章讲 Johnson 算法时会正式登场）：
- 先给每个点随机一个「势」
h[v]； - 造边时先随机一个非负的
w0，再令w(u → v) = w0 + h[u] − h[v]。
于是任意一个环上，所有的 h 首尾相消（望远镜求和）：
Σ w = Σ w0 + (h[环起点] − h[环起点]) = Σ w0 ≥ 0每个环的总长都等于它那些 w0 的和，一定非负 —— 绝不可能有负环。
可单条边的 w 完全可以是负的（h[u] 小、h[v] 大的时候）。
实测：这样造出来的 5288 条边里有 1910 条是负的，而 Floyd 每一轮都给得出答案。
w0 的上限就是「负权浓度」的旋钮，也调过（./genNeg 种子 上限）：
w0 上限 | 负权边 | 朴素 Dijkstra 错的轮数 |
|---|---|---|
| 16 | 959 / 5288 | 16（第 33 轮才第一次抓到） |
| 11 | 1322 / 5288 | 26（第 3 轮） |
| 6 | 1699 / 5288 | 32（第 1 轮） |
| 4（在用） | 1910 / 5288 | 35（第 3 轮） |
10 六种把它写错的方式
前两种第 3 步和第 6 步已经见过了，这里只补上它们在默认图上的输出，然后看后四种。
点「运行 ▶」看结果
跑出 9 10 -1 6 0 2 5 —— 和「拿 BFS 当最短路」一模一样。 它每次取的是编号最小的点，于是 1 号（距离本该是 8）被过早定死在 9， 它的下游 2 号跟着一起错。
★ 它有一半是对的：dist[1] 后来确实被改回了 8（松弛照做），
但已经出过堆的点不会再往下传播。
⚠ 「只错一部分」的版本，比全错的更难发现 —— 这正是要拿它对拍的理由。
点「运行 ▶」看结果
跑出 9 -1 -1 -1 0 2 -1 —— 错得触目惊心。 起点的距离是 0，是全场最小的，所以每一轮挑出来的都是起点， 松弛了 n 遍同样的几条边，图上其余部分根本没被碰过。
和上一份放在一起看：bug 的「可见度」有天壤之别。 这一份第 1 轮对拍就死，上一份要到第 4 轮。
点「运行 ▶」看结果
跑出 12 16 -1 19 0 6 9 —— 七个数里只有起点是对的。 默认那张图里有两处能让它现形，而且是两种不同的机理：
- 重边：
5 → 6有两条（长 2 和长 6）。正确的松弛第二次看一眼 6 > 2 就走了， 这一份把 6 号从 2 改成了 6 —— 而 6 号是整条链的起头，下游全跟着涨。 - 回指的边：
2 → 4，2 号距离 9、4 号距离 6。正确的松弛看一眼 9 + 3 = 12 > 6 就走了， 这一份把一个已经算对的距离改成了 12。
★ 所以它其实是给生成器出的两道题：数据里得有重边，也得有「从远处指回近处」的边。 只造「越走越远、而且没有重边」的图（这正是「顺手写个简单 DAG」的样子），它就隐身了。
点「运行 ▶」看结果
跑出 8 9 1061109567 6 0 2 5 —— 那个 1061109567 就是 0x3f3f3f3f。
六个里它最不「聪明」，算法一个字没错，错的是收尾。
留着它是因为它专门用来检验生成器：
数据要是保证了「从起点能走到所有点」，它就 300 轮全对。
这一份最初我是想写成另一个样子的：「不判可达就拿 INF 去松弛」，
以为会把 INF + w 传染出去。
实测发现根本不会。松弛的条件是 dist[u] + w < dist[v]，
而 INF + w 比 INF 大，这一句压根不成立 —— 那份代码和正解一模一样。
（真会溢出成负数的是 INT_MAX 那种写法，那属于未定义行为，不放进教材。）
★ 「我以为它会错」和「它真的错了」之间，隔着一次实测。 这本教材里被同一件事教育的次数已经数不过来了，这是最新的一次。
点「运行 ▶」看结果
跑出 0 1 -1 4 -1 -1 -1。算法一点毛病没有，错的是读题。
它也不是真正的 bug，是一块试金石（第 31 章 wrongIdentity.cpp 那件工具的第二次使用）：
它专门检查生成器有没有把起点固定成 1 号。
第 30 章刚在这上面栽过（「从 1 号出发」在固定起点的数据上是 0 / 300）。 同一个坑，隔了两章又来一次 —— 所以把它立成硬规矩： 凡是题目里出现「起点 / 根 / 第一个」这种角色，就不许让它固定在 1 号。
11 ★ 对拍
300 轮实测，六个错误版本：
| 故意写错的地方 | 被抓 | 第几轮 |
|---|---|---|
| 无条件松弛（忘了「更近才更新」） | 298 / 300 | 第 1 轮 |
| 没排除已确定的点 | 275 / 300 | 第 1 轮 |
| 拿 BFS 当最短路 | 255 / 300 | 第 1 轮 |
| 从 1 号出发（试金石） | 252 / 300 | 第 2 轮 |
| 走不到的点忘了输出 -1 | 51 / 300 | 第 8 轮 |
| 堆里放编号，不是距离 | 42 / 300 | 第 4 轮 |
（第五行那个 51 正好等于「这 300 轮里有 51 轮存在走不到的点」——
它只在有 -1 时才可能错，所以 51 / 51，一轮不漏。这个恒等式也钉在 check:viz 里。）
12 ★ 生成器调了七次，每次只改一处
gen.cpp 带了九个档位（./gen 种子 档位）。种子固定 1..300。
前四档改的都不是数值范围，而是数据的结构和角色分配：
| 档位 | 改了什么 | 有 -1 的轮数 | BFS | 堆放编号 | 没排除 | 无条件松弛 | 忘了 -1 | 从 1 号出发 |
|---|---|---|---|---|---|---|---|---|
| 0（最初） | 边权全 1 + 起点固定 1 号 + 保证处处可达 | 0 | 0 | 4 | 287 | 299 | 0 | 0 |
| 1 | 边权拉开（w ∈ [1,20]） | 0 | 154 | 17 | 292 | 298 | 0 | 0 |
| 2 | 起点不再固定 1 号 | 0 | 154 | 30 | 292 | 298 | 0 | 252 |
| 3 | 不再保证可达（去掉那条串起所有点的链） | 258 | 40 | 1 | 116 | 155 | 258 | 252 |
三处改动，三个 0 变成非 0：154、252、258。
★ 档位 0 那三样，每一样都是「顺手」写出来的，而且每一样都白送了一条题目里没有的性质：
- 边权全写 1（「先跑通再说」）→ 这道题退化成第 30 章的 BFS， 「拿 BFS 当最短路」根本不是 bug；
- 起点写死 1 号（「题目又没说不行」）→ 第 27、30、31 章那条的第四次；
- 保证处处可达（「有一串 -1 看着不像话」）→
-1那一支永远走不到。
⚠ 注意第 1 档：它改的是数值范围，可它要的不是「值域小」也不是「值域大」， 而是 值域不能只有一个数。第 26 章那条「要的是对比度」的回归。
档位 3 把「不再保证可达」换来了 258，可你看那一行的其它列： BFS 从 154 掉到 40，没排除从 292 掉到 116，堆放编号掉到 1。
★ 这是第 31 章那条「某一支占得太多也是坑」的第二次，而且更露骨：
链一去掉，n 只有几个、随机边又可能只有 1 条，
1772 个点里有 1001 个（57%）从起点根本走不到 ——
而走不到的点上所有程序一律输出 -1，别的 bug 就没机会现形了。
修法是把边数的下界往上提。这个旋钮我故意分三次拧：
| 档位 | 边数下界 | 有 -1 的轮数 | BFS | 堆放编号 | 没排除 | 无条件松弛 | 忘了 -1 |
|---|---|---|---|---|---|---|---|
| 3 | +0 | 258 | 40 | 1 | 116 | 155 | 258 |
| 4 | +n | 203 | 115 | 9 | 201 | 253 | 203 |
| 5 | +2n | 112 | 188 | 23 | 258 | 290 | 112 |
| 6 | +3n | 51 | 241 | 36 | 272 | 298 | 51 |
| （试过 +4n，没留） | +4n | 21 | 276 | 54 | 278 | 300 | 21 |
边越多，前面五个越好抓，「忘了输出 -1」越难抓 —— 这是一条权衡曲线，不是「改对了」。 一次拧到位的话，我根本不会知道「拧一格只补回了一半」。
★ 停在 +3n 的理由不是「平均分最高」，而是 让最弱的那一支尽量强： +3n 时最弱的是 36，+2n 时是 23，+4n 时最弱的变成了「忘了 -1」的 21。
第七处改动：在档位 6 之上，把边权值域从 [1,20] 拉到 [1,60]（那就是在用的档位 7）。
| BFS | 堆放编号 | 没排除 | 无条件松弛 | |
|---|---|---|---|---|
| 档位 6（+3n，值域 [1,20]） | 241 | 36 | 272 | 298 |
| 档位 7（+3n，值域 [1,60]） | 255 | 42 | 275 | 298 |
有效。可同一处改动搬到档位 4 上（那就是留作对照的档位 8：+n，值域 [1,60]）：
| BFS | 堆放编号 | 没排除 | 无条件松弛 | |
|---|---|---|---|---|
| 档位 4（+n，值域 [1,20]） | 115 | 9 | 201 | 253 |
| 档位 8（+n，值域 [1,60]） | 112 | 10 | 201 | 253 |
等于没改。
★ 所以这一章多出一条以前没写过的规矩： 一处改动值不值得留，取决于其它旋钮此刻在哪。 调生成器不是「把好点子一条条加上去」 —— 改动之间是会互相吃掉的。 （第 22 章那句「值域小才是灵魂」，在这一章得到的答复是：要看你先把别的调到了哪一档。）
13 这一章可以带走的五样东西
【1】★ 关键一步：取当前最近的、还没定下来的那个点，它的距离当场就定死。 反证只有三句话，而「边长非负」只在其中一处用到 —— 证明断在哪一步，反例就长在哪里（第 20 章那句话的第三次登场）。
【2】边一带权，「一圈一圈往外扩」就不成立了。 BFS 排的是边数，这道题要的是边长之和； 两者一致只在「每条边都一样长」的时候。默认那张图上就是 8 和 9 这两个数。
【3】把第 31 章的小根堆原样搬过来，就是堆优化。 容器一个字没变，变的是往里放什么（编号 → (距离, 编号)） 和什么时候放（入度减到 0 → 距离变小了）。
【4】「Dijkstra 对负权不行」这句话要说准。 不行的不是那份代码，是那句「取出来就定死」。 堆优化那份因为允许「重新入堆」，在负权图上反而给出正确答案（35 / 300 vs 0 / 300）—— 可它已经悄悄变成了优先队列版的 Bellman-Ford，遇上负环根本停不下来。 ★ 「它给了对的答案」和「这个算法成立」，是两件事。
【5】调生成器不是把好点子一条条加上去。
同一处改动（把边权值域拉到 [1,60]），在一档上是 36 → 42，在另一档上是 9 → 10。
一处改动值不值得留，取决于其它旋钮此刻在哪。
以及第 29 章那条又应验一次：口诀要拿实测复核 ——
「稠密图该用朴素」我拧到 m ≈ n² 都没能复现出来，因为 m log n 是个很松的上界
（900 万条边只带来 19847 次入堆）。
第 33 章：最短路二 —— Floyd、Bellman-Ford / SPFA、负环。
这一章欠了三笔账，下一章一起还：
- Floyd 为什么对，以及那个最经典的错误：
k为什么必须在最外层； - 负权的正经办法：Bellman-Ford（松弛 n−1 轮就够了，为什么）和它的队列优化 SPFA —— 你会发现 SPFA 和这一章那份「在负权图上不小心变对了」的堆优化，是同一件事；
- 负环怎么判：第 n 轮还能松弛成功，就有负环。
这一章的
count.cpp里那个POP_LIMIT刹车，到时候可以扔掉了。
14 自测
- 洛谷 P3371 【模板】单源最短路径（弱化版） —— 本章模板题。朴素 O(n²) 就能过，先拿它把三句话写熟
- 洛谷 P4779 【模板】单源最短路径（标准版） —— ★ 同一道题卡了朴素版，必须堆优化。正好把第 7 步那张表在评测机上再验一次
- 洛谷 P1339 [USACO09OCT] Heat Wave G —— 无向图版：一条边存两遍。写完想一想为什么无向图不影响这一章的任何结论
- 洛谷 P1629 邮递员送信 —— ★ 去程一遍 Dijkstra，回程把所有边反向再跑一遍。「反向建图」是很值钱的一招
- 洛谷 P1462 通往奥格瑞玛的道路 —— 进阶：二分答案 + Dijkstra 判可行。第 9 章那套二分答案在图上的第一次登场
- 洛谷 P1073 [NOIP2009 提高组] 最优贸易 —— 进阶：需要分层图 / 正反两遍最短路。想清楚「状态」是什么，这道题就塌了