1. 同是“城市间货物运输”三道题的差异在哪第六十五天的三道题第一眼可能会让人以为只是同一道题换了三种输入输出。其实卡码网 94、95、96 是按同一个背景往下加条件的94 是“有负权边求从城市 1 到城市 n 的最小运费”95 是“如果存在负权回路就不要再算数字了直接输出 circle”96 是“额外限制最多经过多少个城市/多少条边再求最小运费”。如果前几天刚把 Dijkstra 写得顺手今天第一题就会有点别扭因为运输公司为了促进经济会给某些线路补贴补贴后的运费可能是负数。三个版本的核心区别可以用一张表看明白题号在基础模型上加的条件需要练的核心点94边权可能为负Bellman-Ford 基础模板95可能存在负权回路负环判定96限制经过边数/城市数有限轮数的 Bellman-Ford三道题共享同一个核心函数差别其实只在几个 if 和一层循环里。读题时要注意一点这三题在不少平台上的输入格式不完全一样我下面统一按最常见的版本写第一行是城市数量 n 和道路数量 m接下来 m 行是 u v w表示从 u 到 v 的运输成本为 w起点是城市 1终点是城市 n。如果你的题面把起点和终点换成了别的城市把初始化 dist 的地方改一下即可。另外这三题都建议用“边表”而不是邻接表来做。原因是 Bellman-Ford 每一轮都要把所有边完整扫一遍边表存起来最直接也最不容易写乱。2. 把 Dijkstra 放下负权边为什么必须用逐轮松弛很多人看到最短路第一反应就是 Dijkstra但负权边会直接破坏 Dijkstra 的贪心基础。Dijkstra 的核心是“从优先队列里弹出最小距离的节点然后把它锁死”。这个逻辑在边权非负时是对的因为不可能还有一条更大的中间距离能绕回来把这个已锁节点的距离改小。可一旦边权可为负这句保证就失效了。2.1 一个让 Dijkstra 锁错节点的负权例子看这个三城市的小图1 - 2运费 31 - 3运费 43 - 2运费 -10从城市 1 到城市 2 的最优路线是先到 3再到 2总费用是 4 (-10) -6。Dijkstra 初始化后 dist[2] 3dist[3] 4优先队列会先弹出城市 2然后把它标记为已访问。等到处理城市 3 的时候发现边 3 - 2 能带来更低的 -6但城市 2 已经被锁死更新不进去最终输出 3。这个例子不是特例只要存在“一条负权边指向某个已经被锁定的节点”Dijkstra 就可能出错。Bellman-Ford 之所以能处理就是因为它从来不锁节点而是每一轮把所有边重新看一遍只要还能压低就更新。你可以把它理解成每天都把市场上所有报价重新比对一遍而不是看一眼就拍板。2.2 松弛一轮到底在做什么Bellman-Ford 的核心操作叫“松弛”。对于每条边 u - v权重为 w如果当前已知到 u 的运费 dist[u] 加上 w比当前已知到 v 的运费 dist[v] 更小就更新 dist[v]。写成伪代码就是if (dist[u] ! INF dist[u] w dist[v]) { dist[v] dist[u] w; }所谓“一轮松弛”就是把所有 m 条边从上到下完整扫一遍。一轮结束后如果没有任何更新说明已经收敛可以提前 break。如果存在负权回路它永远不会收敛所以必须要有一个循环上限。为什么上限是 n - 1 轮因为在一个没有负环的图里从起点到任意节点的最短路一定是一条简单路径简单路径最多经过 n - 1 条边。每多扫一轮其实就是在允许更多信息继续向后传播。跑到 n - 1 轮还收敛不了唯一的解释就是有负环能反复压低距离这就是 95 题的切入点。3. 94 题落地边表 n-1 轮松弛就是完整模板94 题本身不复杂但它值得当成 Bellman-Ford 的“母版”。后面所有变体都是在这段代码上做加法所以每一行都要吃透。3.1 为什么只需要存边不需要建邻接表Bellman-Ford 不依赖从某个点出发去遍历邻接边它只关心“这条边能不能更新”。你不需要知道 u 的邻居有哪些只需要知道每条边的 u、v、w。所以直接开一个结构体数组存边即可。struct Edge { int u, v; long long w; };这里需要提醒一句如果题目里的“道路”是双向的也就是汽车可以往返走那么每条道路要拆成 u - v 和 v - u 两条有向边再存入边表如果题目本来就写的是“单向运输线路”那就直接按输入存。3.2 完整代码#include bits/stdc.h using namespace std; struct Edge { int u, v; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } const long long INF 1e18; vectorlong long dist(n 1, INF); dist[1] 0; for (int round 0; round n - 1; round) { bool updated false; for (const auto e : edges) { if (dist[e.u] ! INF dist[e.u] e.w dist[e.v]) { dist[e.v] dist[e.u] e.w; updated true; } } if (!updated) break; } if (dist[n] INF) { cout unconnected endl; } else { cout dist[n] endl; } return 0; }注意dist[e.u] ! INF这个判断不能省。如果不判断一个不可达节点带着 INF 去加一条负权边会把另一个节点更新成一个看似很小的数最后答案就是错的。这题的输出结果也可能是负数这是正常现象。不要看见负数就觉得“路径不存在”负权本来就是允许的只要没有负环这个负值就是合法的最小运费。4. 95 题n-1 轮之后再扫一次负环就藏不住95 题是在 94 的基础上增加一个判断如果图中存在负权回路就直接输出 circle。所谓负权回路就是一条从某个点出发、经过若干条边后回到自己、并且总权重为负的环。比如 1 - 2 权值为 -12 - 3 权值为 -13 - 1 权值为 -1这就是一个总权 -3 的负环。4.1 负环为什么让最短路不存在原因是环上每绕一圈总运费都会再降低绕的次数越多费用越低。如果没有额外限制答案会趋向负无穷所以“最小运费”这个说法本身就不成立。因此题目才会要求一旦检测到负环不要输出数字而是输出 circle。检测负环的方法非常朴素在跑完 n - 1 轮标准松弛之后再额外扫一遍所有边。如果这一遍还有边能继续更新说明图中存在从源点可达的负环。原因是在没有负环的图里n - 1 轮已经足够让所有最短距离稳定下来还能更新只能说明有一条负权回路在反复压低距离。4.2 检测与输出顺序95 的完整代码和 94 只差最后一段。前面 n - 1 轮松弛保持不变后面加一次扫描bool hasNegativeCircle false; for (const auto e : edges) { if (dist[e.u] ! INF dist[e.u] e.w dist[e.v]) { hasNegativeCircle true; break; } } if (hasNegativeCircle) { cout circle endl; } else if (dist[n] INF) { cout unconnected endl; } else { cout dist[n] endl; }输出顺序不要写反。一旦有负环城市之间的最短费用已经没有意义所以要优先输出 circle再去判断 unconnected 和具体数值。4.3 负环不在源点可达区怎么办这里有一个初学者不太注意的细节上面的写法只会检测“源点 1 能到达的负环”因为松弛条件里写了dist[e.u] ! INF。如果一个负环藏在图里但城市 1 根本走不到那个环上的节点那么这个负环不影响从 1 出发的任何路线。如果题目只要求“判断整个图是否存在负环”那就要把所有节点的初始距离都设成同一个值比如都设为 0再跑一遍 Bellman-Ford。但这样就不能顺便求从 1 到 n 的最短路了因为所有起点都被激活了。实际上绝大多数题目问的是从源点出发能不能碰到负环所以保留dist[1] 0的写法更贴合场景。如果更严格地问“负环是否真的能让城市 1 到城市 n 的费用无限降低”那还需要判断负环上的点能否到达终点 n做法是反向建图做一次可达性检查。初学阶段可以先把基础负环判断写稳再按需扩展。5. 96 题限制经过边数时一个备份数组是关键96 题看起来只是加了一个 K 的限制但写法上有个特别容易踩的坑不能用标准 Bellman-Ford 的原地更新方式来数轮数。5.1 标准原地松弛为什么会在同一轮“偷跑”看一个小图1 - 2运费 12 - 3运费 11 - 3运费 10假设现在要求从 1 到 3 最多经过 1 条边那答案应该是直接走 1 - 3费用 10。如果直接用 94 的原地松弛代码第一轮扫描时先处理 1 - 2把 dist[2] 更新成 1紧接着处理 2 - 3 时发现 dist[2] 已经不是 INF 了于是又用刚算出来的 1 去更新 dist[3]把它更新成 2。这一轮里其实已经连续走了两条边1 - 2 - 3。但标准 Bellman-Ford 的原地更新是允许这种链式传播的它会让收敛更快却不适合用来限制“最多经过几条边”。所以 96 题必须做数组备份。5.2 备份数组 限定轮数的实现核心改动是每一轮开始前把当前 dist 复制一份到 old然后这一轮所有松弛都从 old 读取旧值只向当前 dist 写入新值。这样一轮最多只能“往前走一条边”不会出现同一条路径在内部连环传递的情况。#include bits/stdc.h using namespace std; struct Edge { int u, v; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } int k; cin k; const long long INF 1e18; vectorlong long dist(n 1, INF); dist[1] 0; for (int round 0; round k; round) { vectorlong long old dist; bool updated false; for (const auto e : edges) { if (old[e.u] ! INF old[e.u] e.w dist[e.v]) { dist[e.v] old[e.u] e.w; updated true; } } if (!updated) break; } if (dist[n] INF) { cout unconnected endl; } else { cout dist[n] endl; } return 0; }关键就在于vectorlong long old dist;这一行。很多人第一次写会写成auto old dist;那就没有备份效果了。必须是一份独立的拷贝才能保证这一轮内不会读到本轮刚更新的结果。5.3 K 到底是边数还是中转城市数96 题的 K不同版本含义不一样。有的题目说“最多经过 K 条边”那轮数就是 K有的题目说“最多经过 K 个中转城市”那从起点到终点需要 K 1 条边轮数就要改成 K 1。写代码之前先拿样例对一下如果样例里一步直达就能到终点但 K 0说明 K 是中转次数如果一步直达需要 K 1说明 K 是边数。这个细节很容易让代码在本地看起来没问题、一提交就 WA。6. 提交前别忽略的边界和几个易错点三道题都刷完之后我复盘时发现真正容易错的往往不是算法主流程而是几个边界处理。这里集中列一下。6.1 unreachable 和 INF 的判断凡是判断“不可达”都要用dist[终点] INF来表示。不要用dist[终点] 0来判断不可达因为负权边会让正确答案本身就是负数。也不要忘记在松弛时判断dist[u] ! INF否则不可达节点会把 INF 传给其他节点。如果题目给的数据范围比较大边权累加可能超过 int建议直接用 long long。用 int 存运费时一旦遇到多段负权累加很容易溢出成奇怪的负数然后整段逻辑都乱掉。6.2 n 1 和自环如果城市数量只有 1也就是起点和终点相同那么 94 题的答案应该是 0。代码里 n - 1 0循环一次都不跑直接输出 dist[n]也就是 0行为是正确的。但如果 95 题里出现一条 1 - 1 的负权自环说明存在负权回路。这时 n - 1 0但负环检测那段仍然会扫一次边发现 0 (-w) 0就能正确输出 circle。所以负环检测代码不要放在循环内部一定要放在 n - 1 轮循环结束之后单独执行。6.3 提前退出的位置我见过有人把“提前退出”写到了边循环里面比如一条边更新后立刻 break。这是错的。每一轮必须把全部边扫完才能判断本轮有没有更新。正确的写法是先用updated标记本轮是否有更新等整轮边表扫完后再检查。这个错误在 94 题不容易被发现因为数据弱时可能也能过但在 95 题负环检测中扫描不完整会漏判导致该输出 circle 的时候输出了一个数字。6.4 我提交前会做的三组测试这组检查是我自己总结出来的虽然简单但每次提交前都能拦住低级错误。第一组跑一遍题目样例确认输出格式里的 unconnected、circle 这些单词拼写和大小写没问题。第二组把图中所有负权边临时改成正权用 Dijkstra 的答案对拍因为此时 Bellman-Ford 的结果应该和 Dijkstra 完全一致。第三组自己构造一个“从 1 出发能绕一圈回到 1 且总权为负”的数据看 95 题是否稳定输出 circle再看 96 题把 K 设成 1 和设成很大的数时答案是否符合直觉。这三组测试做完Bellman-Ford 的三道变体基本就可以放心提交了。尤其是第三组它能同时验证你对负环、有限步数、提前退出这三个点的理解是否到位。