学习目标

• 能复述教材 7.3 节"负边为什么摧毁 Dijkstra"的反例机理；
• 能实现 Bellman-Ford 的 $n-1$ 轮全边松弛；
• 能用第 $n$ 轮是否仍能松弛检测从源点可达的负环；
• 能处理无穷大哨兵参与松弛时的溢出问题。

前置知识

先读第 7.3 节最短路径中"它也有软肋：负权边"小节，并完成 Lab 07-10。本题解决的是 Dijkstra 唯一不敢接的场景：边权可以为负。

为什么需要新算法

Dijkstra 的确定性不变量"出队即最终"依赖路径前缀不超过整条路径，而这条性质在负权尾段下失效。教材的经典反例：

0 → 1  权 1
0 → 2  权 2
2 → 1  权 -2

真实最短路 $d(0,1)=0$（走 0→2→1，$2+(-2)=0$），但 Dijkstra 第一轮就把 1（估计 $1$）当成最终答案盖章了。Bellman-Ford 的应对是不相信任何一次松弛：把全部边无差别地松弛 $n-1$ 轮，每轮必然把"正确距离"沿最短路向前推进至少一跳。

Bellman-Ford 算法

对边表 edges[0..m)，重复 $n-1$ 轮：

for i in 1..n-1:
    for each edge (u, v, w) in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            prev[v] = u

• 为什么 $n-1$ 轮够：一条最短路径至多有 $n-1$ 条边（无负环时，任何顶点不会在最短路上出现两次）。第 $i$ 轮结束时，所有"恰好用 $\le i$ 条边即可走通的最短路"都已收敛。
• 负环检测：再做第 $n$ 轮，仍须先判断 dist[u] != INF；若仍有一条可达边能松弛，说明存在一条从源点可达的总权为负的闭路（负环），最短距离无下界，输出 NEGATIVE CYCLE。

输入格式

第一行三个整数 n m s：顶点数、有向边数、源点编号。

接下来 m 行，每行三个整数 u v w，表示 u -> v 的有向边，边权 w 可以为负。

输入保证：

• 1 <= n <= 1000；
• 0 <= m <= 3000；
• 0 <= u, v < n；
• 0 <= s < n；
• -10^4 <= w <= 10^4；
• 边权范围保证任何有限 dist 都在 long long 内。

输出格式

若存在从源点可达的负环，输出一行：

NEGATIVE CYCLE

否则输出两行：

第一行 n 个整数 dist[i]（不可达输出 -1）；

第二行 n 个整数 prev[i]（源点与不可达顶点输出 -1）。

样例输入 1（教材反例，含负边无负环）

4 5 0
0 1 1
0 2 2
2 1 -2
1 3 5
2 3 8

样例输出 1

0 0 2 5
-1 2 0 1

样例解释 1

$d(0,1)=0$ 来自 $0\to 2\to 1$（$2+(-2)=0$），前驱是 2。$d(0,3)=5$ 走 $0\to 2\to 1\to 3$（$2-2+5=5$）。这正是 Dijkstra 算错的那个图——负权边迫使路径先绕远再抄近路。

样例输入 2（含负环）

3 3 0
0 1 1
1 2 -3
2 1 1

样例输出 2

NEGATIVE CYCLE

样例解释 2

环 1→2→1 总权 $-3+1=-2<0$，从 0 可达。每绕一圈 0→1→2→1→2→… 到 2 的距离都再降 2，最短路径失去下界。

任务

1. 读入边表（按数组顺序存储，直接对边表反复松弛，不建邻接表）；
2. 初始化 dist[s]=0，其余无穷；
3. 松弛 $n-1$ 轮，维护 prev；
4. 第 $n$ 轮再扫一遍全部边：若仍能松弛，输出 NEGATIVE CYCLE；
5. 否则输出 dist 与 prev（无穷与源点输出 -1）。

正常、边界与错误情况

情况	预期行为
含负权但无负环	正确输出最短路
负环从源点不可达	不影响结果，不报负环（仅当松弛更新可达时触发）
负权自环	若 w<0 且从源点可达，即负环，必然触发检测
零权边	正常处理
n==1 且无边或无可达负环	输出 0 与 -1
n==1 且存在可达负权自环	输出 NEGATIVE CYCLE
松弛读无穷	必须先判断 dist[u] 有限，避免 INF + 负权 溢出

运行与评分

在本 Lab 目录执行：

make doctor
make run
make run CASE=001-sample
make score

未安装 Make 时，在仓库根目录执行：

pnpm lab:doctor -- labs/chapter-07/exercise/E-07-11-bellman-ford-negative
pnpm lab:run -- labs/chapter-07/exercise/E-07-11-bellman-ford-negative
pnpm lab:score -- labs/chapter-07/exercise/E-07-11-bellman-ford-negative

完成清单

• 全部测试用例通过；
• 松弛前判断 dist[u] 有限，INF 不参与 +w 运算；
• 第 $n$ 轮检测在完整 $n-1$ 轮之后进行；
• 只有"从源点可达"的负环才输出 NEGATIVE CYCLE；
• prev 在负环检测后不再更新（直接输出标记）。

复杂度分析

$n-1$ 轮 × 每轮 $m$ 条边 = $O(nm)$ 时间，$O(n+m)$ 空间。相比 Dijkstra 的 $O((n+m)\log n)$ 慢不少，但它能处理负权。能用 Dijkstra 就别用 Bellman-Ford——先用 7.3 节的选型表判断图的性质。

思考与复盘

1. 反例图中，Dijkstra 具体在哪一步出错？对应的证明步骤"前缀 ≤ 全长"在哪一步断裂？

查看参考答案

从 0 出发时，dist[1]=1、dist[2]=2，Dijkstra 会先确定顶点 1。随后处理 2→1(-2) 才发现距离应为 0，但 1 已被错误地确定。路径 0→2→1 的前缀长度是 2，反而大于全路径长度 0；负边正是在这里打破了证明所需的“前缀不超过全长”。

2. 为什么 $n-1$ 轮"一定够"？$n$ 条边的最短路里为什么必然有重复顶点？

查看参考答案

没有负环时，总能选择一条不重复顶点的最短路：若路径重复顶点，其中夹着的回路权重非负，删除它不会让路径变长。简单路径最多经过 n 个顶点，因此至多有 n-1 条边。若一条路径有 n 条边，就经过 n+1 次顶点访问，按抽屉原理必有顶点重复。

3. 若负环从源点不可达，为什么第 $n$ 轮检测不会误报？

查看参考答案

初始化后只有源点距离有限，松弛前又跳过 dist[u]==INF 的边。不可达负环中的所有顶点始终保持无穷，不会参与任何松弛，因此第 $n$ 轮不会因它而报告负环。

4. Bellman-Ford 与 Floyd 都能检测负环，检测方式分别是什么？各自更擅长哪种图？

查看参考答案

Bellman-Ford 在完成 n-1 轮后再扫一轮；从给定源点可达的边仍能松弛，就有可达负环。Floyd 完成三重循环后检查是否存在 d[i][i] < 0。前者适合单源、稀疏图，时间为 $O(nm)$；后者一次得到全源结果，适合顶点较少、稠密或本就需要多点对查询的图，时间为 $O(n^3)$。