企业官网建设流程全解析

多段图的最短路径是算法课里少数几个"看到结构就知道该用什么"的题型。只要题目里出现"顶点可以划分成若干段、边只能从第 i 段指向第 i+1 段"这类描述，基本可以立刻判定：这是动态规划的送分题，不需要 Dijkstra，不需要堆优化，一段循环倒着推一遍就完事。但真到期末编程题或者面试白板上，翻车的人一点都不少——有人把顶点编号当成了段号，有人 INF 加出负数，有人只输出了一条路径却被要求列出所有最优解。这篇就把多段图最短路径从建模、状态定义、递推、决策记录到代码落地整条链路讲清楚，顺带把几个我实际踩过的坑摊开说，无论你是刚学动态规划的新手，还是回头复习算法设计的同学，都能直接照着复现。

1. 先把"多段图"这个词拆开：顶点分层与边的走向

1.1 从一张物流转运表看多段图的真实长相

多段图（Multistage Graph）听起来抽象，换成物流场景就很好理解了。假设一批货从产地发往销地，中间必须经过若干个转运枢纽，第一站只能进"集货中心"，第二站只能进"区域分拨"，第三站只能进"城市配送站"，最后到客户手里。每个阶段的候选节点是明确的，而且货只能一站一站往前推，不能从区域分拨倒回集货中心。这就是多段图的本质：顶点集合被划分成 k 个互不相交的子集，边只从第 i 段指向第 i+1 段。

形式化一点说，给定有向图 G=(V,E)，若存在 V 的一个划分 V1, V2, ..., Vk，使得对任意边 (u,v)∈E，若 u∈Vi，则必有 v∈V(i+1)，这样的图就叫 k 段图。通常约定 V1 只有一个源点 s，Vk 只有一个汇点 t，中间段的顶点数量不限。为什么强调"源点唯一、汇点唯一"？因为这两个约束直接决定了递推的起止位置——你总得有个地方开始填表，也得有个地方让表收敛。

我在实际做题时发现，很多人读题漏掉"边只从第 i 段指向第 i+1 段"这句，把图当成普通带权有向图去做，堆优化 Dijkstra 写了一百行，结果答案还是对的，但老师要看的是 DP 过程，分就没了。所以第一步永远是确认这张图到底是不是多段图，判断标准很简单：能不能给每个顶点标一个段号，使得所有边都满足"段号 +1"。如果存在同段之间的边，或者跳跃多段的边，那就不是标准多段图。

1.2 为什么"无环"这个附加条件才是DP的通行证

多段图的边只能往下一段走，这个结构天然保证了图中不存在环。这一点非常关键，因为动态规划能用的前提，就是子问题之间必须有明确的拓扑顺序，不能互相依赖。如果有环，你算 A 需要 B，算 B 又需要 A，递推就死锁了，只能改用 Bellman-Ford 这类迭代松弛的办法。

无环带来的直接好处是：我可以给所有顶点排出唯一的推进顺序。反向递推时从汇点往前推，正向递推时从源点往后推，每一段的顶点在计算时，它所依赖的下一段（或上一段）结果一定已经算好了。这就是所谓的"无后效性"——顶点 u 的最优决策只取决于它自己到汇点的边的权重，以及下一段顶点的最优值，跟前面怎么走到 u 的完全无关。

打个比方，这就像做菜。如果你要做红烧肉，你得先焯水、再炒糖色、再炖，每一步都依赖前一步的产物，顺序明确，不会出现"炖到一半发现还得回去焯水"的情况。动态规划的递推数组就是这些半成品，按依赖顺序摆好，用的时候直接取。

1.3 段与段之间跳过了怎么办：阶段划分的两种常见口径

教材里画的多段图通常很规整，段与段之间边线清清爽爽。但实际题目里，经常出现从第 2 段直接连到第 4 段的边，或者中间某段只有一两个顶点。这时候阶段划分就有两种处理口径：

我个人的习惯是：如果题目已经给了段划分，就老实按段循环；如果只给了图和边，先跑一遍拓扑排序确定层级，再按层递推。千万别自己凭顶点编号猜段号，这是后面第 5 章要专门讲的坑。分层这件事在写代码时建议用二维列表stages = [[...], [...], ...]显式存下来，比每次用条件判断去算要清晰得多，调试的时候也能直接打印出每段的顶点，肉眼核对。

2. 反向递推的坐标：cost数组和决策数组各管什么

2.1 状态定义的那一句话决定了后面所有代码

解多段图最短路径，第一步是把状态定义写成一句中文。我习惯这么写：cost[i] 表示从顶点 i 出发，沿任何一条合法路径走到汇点 t 的最小总权值。注意是"从 i 出发"，也就是说这个状态描述的是"剩余路程"的最优值，而不是"已经走过的路程"。这个方向选对了，边界条件就非常干净：cost[t] = 0，因为从汇点走到汇点不需要任何花费。

定义完状态，递推方程自然就出来了：

cost[i] = min{ w(i, j) + cost[j] } ，其中 (i,j) ∈ E

这里的 w(i,j) 是边权，cost[j] 是下一段的已知结果。整个式子翻译成人话就是：从 i 出发的最短路，等于"随便挑一条出边走出去，花掉的边权，加上从那个落点继续走到终点的最优值"，在所有出边里取最小的那个。

你要是选另一种定义也不违法，比如定义 cost[i] 为"从源点走到 i 的最短距离"，那就是正向递推，边界变成 cost[s] = 0，递推式变成 cost[j] = min{ cost[i] + w(i,j) }。两种定义数学上等价，但反向后推的好处是不需要额外的前驱数组就能直接回溯路径，正向则必须额外存 prev。这也是为什么大多数教材默认讲反向版本。

2.2 决策记录：一维nxt够不够，什么情况下必须上二维path

只求出一个最短距离数字，一维的 cost 数组就够了。但题目一旦加一句"输出最短路径"，你就必须额外记录决策。这里有个分层：

• 只要求输出任意一条最短路：用一维数组nxt[i]记录顶点 i 在最优方案下走到的下一跳，最后从源点沿着 nxt 一路跳过去即可。
• 要求输出所有最短路：一维不够，必须改成best_next[i] = [v1, v2, ...]，把所有满足w(i,v) + cost[v] == cost[i]的 v 都收集起来，再用 DFS 展开。

很多教材里出现的path二维数组，比如path[i][j]，其实是另一种口径：把顶点按"第 i 段第 j 个"来编号，path 存的是这一格该往哪个顶点走。这种二维写法在人工手算时特别舒服，因为表格一摊开就能逐格填，但写成代码反而绕。我一般只在黑板上手推时用二维，落到代码里还是老老实实用一维加列表。

这里必须提醒一句：用一维 nxt 记录时，如果直接写if (new < cost[u]) { cost[u] = new; nxt[u] = v; }，遇到相等的情况不更新，就会丢掉并列最优解。这道题里最短路可能不止一条，比如下面第 3 章要手推的例子就有两条长度相同的路径。想要全部输出，判断条件必须写成"小于则清空重记，等于则追加"，这个细节后面 5.3 会展开。

2.3 边界、INF与初始化：三个最容易写反的地方

第一个是汇点的初始化。cost[t] 一定是 0，不能是 INF。有些同学图省事，把整个 cost 数组初始化为 INF，然后忘记把汇点改成 0，结果所有计算出来都是 INF + 权重，输出一个大得离谱的数。

第二个是不可达的处理。如果某个顶点 i 没有任何出边能通向汇点，它的 cost 应该保持 INF，并且在参与上一段的 min 比较时被自然排除。注意这里隐含一个前提：INF 加上任意有限边权后，结果仍然要被认为是"不可达"。在 Python 里 float('inf') 加任何数还是 inf，天然没问题；但在 C 或 Java 里用 int 存 INF，就可能溢出成负数，反而被 min 选中，输出一个荒谬的负距离。这个坑 5.2 单独讲。

第三个是迭代顺序的边界。反向递推从倒数第二段开始，一直推到第 1 段。如果段索引从 0 开始，循环就是for k in range(len(stages)-2, -1, -1)，很容易写成range(len(stages)-1, -1, -1)，多算了一次汇点所在段，虽然结果不受影响，但逻辑上不干净。正向递推同理，从第 2 段推到第 k 段。

3. 拿一张12个顶点的图手推一遍：从汇点倒着填到源点

3.1 建图与阶段表

光看公式容易飘，找一张经典例题推一遍最踏实。取一个 5 段图的例子，顶点编号 1~12，段划分为：

• V1 = {1}
• V2 = {2, 3, 4, 5}
• V3 = {6, 7, 8}
• V4 = {9, 10, 11}
• V5 = {12}

边和权值如下表：

这张图的好处是它同时包含了两种典型情况：从第 1 段到第 2 段的边比较密集，而第 3 段到第 4 段、第 4 段到第 5 段的边比较稀疏，能覆盖"顶点无出边"和"多个最优解并列"两种情形。

3.2 逐段填cost表，每一步都写清楚比较过程

从最后一段往前推。汇点是 12，cost[12] = 0。

先处理第 4 段 {9, 10, 11}：

• 顶点 9：唯一出边 9→12 权 4，cost[9] = 4 + 0 = 4，决策记为 12。
• 顶点 10：唯一出边 10→12 权 2，cost[10] = 2 + 0 = 2，决策记为 12。
• 顶点 11：唯一出边 11→12 权 5，cost[11] = 5 + 0 = 5，决策记为 12。

再处理第 3 段 {6, 7, 8}：

• 顶点 6：两条出边。走 9 是 6 + cost[9] = 6 + 4 = 10；走 10 是 5 + cost[10] = 5 + 2 = 7。取小值 7，决策记为 10。
• 顶点 7：走 9 是 4 + 4 = 8；走 10 是 3 + 2 = 5。取 5，决策记为 10。
• 顶点 8：走 10 是 5 + 2 = 7；走 11 是 6 + 5 = 11。取 7，决策记为 10。

第 2 段 {2, 3, 4, 5}：

• 顶点 2：走 6 是 4 + 7 = 11；走 7 是 2 + 5 = 7；走 8 是 1 + 7 = 8。取 7，决策记为 7。
• 顶点 3：走 6 是 2 + 7 = 9；走 7 是 7 + 5 = 12。取 9，决策记为 6。
• 顶点 4：唯一出边到 8，11 + 7 = 18，决策记为 8。
• 顶点 5：走 7 是 11 + 5 = 16；走 8 是 8 + 7 = 15。取 15，决策记为 8。

第 1 段 {1}：

• 顶点 1：走 2 是 9 + 7 = 16；走 3 是 7 + 9 = 16；走 4 是 3 + 18 = 21；走 5 是 2 + 15 = 17。

最小是 16，而且出现了一次并列：走 2 和走 3 都能得到 16。这就是前面反复提到的多解情况。

把结果整理成一张表看得更清楚：

3.3 回溯出两条等价最优路径

从源点 1 顺着最优下一跳走，因为顶点 1 有两个并列决策，所以有两条路径：

• 1 → 2 → 7 → 10 → 12，总权值 9 + 2 + 3 + 2 = 16
• 1 → 3 → 6 → 10 → 12，总权值 7 + 2 + 5 + 2 = 16

两条路径长度完全一致。如果你写的程序只吐出来第一条，不是算法错了，而是决策记录那块用了单值覆盖的写法。另外注意，中间顶点 7 和 6 的最优决策都指向 10，这是巧合也是必然——10 到汇点的代价只有 2，是第 4 段里最便宜的落点，所以第 3 段的顶点天然都想往它身上靠。

手工推这一步的价值在于：你能亲眼看到"最优子结构"是怎么在两段之间传递的。顶点 6 之所以知道走 10 划算，完全依赖 cost[10] 这个已经算好的值；如果顺序颠倒过来先算第 3 段再算第 4 段，cost[10] 还是 INF，结果全错。

3.4 如果反过来从源点正推，表会长什么样

同一张图用正向递推（dist[i] 表示源点到 i 的最短距离）也能得到 16，过程如下。

dist[1] = 0。第 2 段：

• dist[2] = dist[1] + 9 = 9，前驱 1
• dist[3] = dist[1] + 7 = 7，前驱 1
• dist[4] = dist[1] + 3 = 3，前驱 1
• dist[5] = dist[1] + 2 = 2，前驱 1

第 3 段：

• dist[6] = min(dist[2]+4, dist[3]+2) = min(13, 9) = 9，前驱 3
• dist[7] = min(dist[2]+2, dist[3]+7, dist[5]+11) = min(11, 14, 13) = 11，前驱 2
• dist[8] = min(dist[2]+1, dist[4]+11, dist[5]+8) = min(10, 14, 10) = 10，前驱 2 或 5 并列

第 4 段：

• dist[9] = min(dist[6]+6, dist[7]+4) = min(15, 15) = 15，前驱 6 或 7
• dist[10] = min(dist[6]+5, dist[7]+3, dist[8]+5) = min(14, 14, 15) = 14，前驱 6 或 7
• dist[11] = dist[8] + 6 = 16，前驱 8

第 5 段：

• dist[12] = min(dist[9]+4, dist[10]+2, dist[11]+5) = min(19, 16, 21) = 16，前驱 10

结果同样是 16。可以看出正向递推的并列情况更多，回溯路径时要沿着前驱数组倒着走，代码上比反向的 nxt 链要绕一点。如果题目只要求长度，两种写法随便挑；如果要求输出路径，我强烈建议用反向，因为 cost 和 nxt 天然是一条顺着走的链，从源点一路打出来就是答案，不用 reverse。

4. 代码落地：三种实现写法的取舍与踩坑

4.1 邻接矩阵与邻接表的选择依据

存储结构这件事，多段图里有明确结论：稠密用矩阵，稀疏用邻接表。上面那张 12 顶点的例子，总共 19 条边，V² = 144，用矩阵会浪费大量空间，而且反向递推时如果偷懒写成"遍历所有顶点 v，看 adj[u][v] 是不是 INF"，复杂度会变成 O(V²) 而不是 O(E)。多段图真正优雅的地方在于：顶点 u 的合法后继必然落在下一段里，所以只需要遍历stages[k+1]这个列表即可，复杂度严格是 O(V + E)。

我见过不少答案代码长这样：

for u in stages[k]: for v in range(n): if adj[u][v] < INF: ...

逻辑没错，但把一个 O(E) 的算法写成了 O(V²)。期末题数据量小的时候看不出来，一旦顶点数上去，差距就拉开了。更稳的写法是把邻接表直接按边存好：

# edges[u] = [(v, w), ...] 只包含合法的下一跳 edges = {1: [(2,9), (3,7), (4,3), (5,2)], 2: [(6,4), (7,2), (8,1)], ...}

这样既省内存，又顺便把"非法边"过滤掉了，不用每次都判断 INF。

4.2 反向DP的完整Python实现（逐行说清）

下面这份实现，假设顶点用 0 起始编号，stages 按顺序给出每一段的顶点列表，最后一段只有一个汇点。

INF = float('inf') def multistage_shortest(n, stages, edges): """ n : 顶点个数，编号 0 ~ n-1 stages: 二维列表，stages[k] 是第 k 段的顶点，按段前缀顺序 edges : 字典，edges[u] = [(v, w), ...]，v 必须在 u 的下一段 返回 : (最短距离, 最优下一跳列表字典) """ cost = [INF] * n nxt = [[] for _ in range(n)] sink = stages[-1][0] cost[sink] = 0 # 从倒数第二段开始，逐段向前推进 for k in range(len(stages) - 2, -1, -1): for u in stages[k]: best = INF for v, w in edges.get(u, []): cand = w + cost[v] if cand < best: best = cand nxt[u] = [v] # 发现更优，清空重记 elif cand == best: nxt[u].append(v) # 并列最优，追加 cost[u] = best # 如果 best 仍是 INF，说明 u 无法到达汇点，保持不可达 return cost[stages[0][0]], nxt

几个值得停下来看的点。

第一，nxt初始化成列表的列表，而不是单个整数。原因在 2.2 已经说过，这是为了保留并列最优解。如果你只想输出一条，可以退化成单个整数，代码少两行，但功能就残缺了。

第二，判断条件的顺序很讲究。必须是"先判小于、再判等于"，而且小于的时候要清空再追加。写反了、或者只写小于不写等于，都会丢掉路径。这个逻辑跟 Dijkstra 里记录多条最短路是一模一样的套路。

第三，edges.get(u, [])用了默认空列表，是为了处理"某段顶点没有任何出边"的边界情况。这种情况下 u 会保持 INF，符合预期。

4.3 正向DP：把状态换成"从源点到i的最短距离"

正向版本适合你想复用拓扑序、或者题目本身就要求从源点算起的场景：

def multistage_forward(n, stages, redges): """ redges[u] = [(p, w), ...] 表示"从 p 指向 u 且权为 w"的入边 返回 (源点到汇点最短距离, 前驱列表) """ INF = float('inf') dist = [INF] * n prev = [[] for _ in range(n)] src = stages[0][0] dist[src] = 0 for k in range(1, len(stages)): for v in stages[k]: best = INF for p, w in redges.get(v, []): cand = dist[p] + w if cand < best: best = cand prev[v] = [p] elif cand == best: prev[v].append(p) dist[v] = best return dist[stages[-1][0]], prev

这份实现的时间复杂度同样是 O(V + E)，空间 O(V)。区别只在于递推方向不同，以及记录的是前驱而不是后继。我个人更偏好反向版，理由前面说过：输出路径时不用 reverse，直接顺着 nxt 打印就行，读起来更符合"从起点出发一路走到底"的直觉。

如果非要给性能排个序，两种写法在同一张图上没有实质差异，都是线性对边。所谓"正向更快"的说法在这个问题上不成立，除非你的数据是流式给出的、必须边读边算，那另说。

4.4 输出全部最短路：决策数组要从单值改成列表

拿到 nxt 之后，输出所有最短路的写法就是一个简单的 DFS：

def enumerate_paths(nxt, src, sink, path=None, res=None): if path is None: path, res = [src], [] if src == sink: res.append(list(path)) return res for nv in nxt[src]: path.append(nv) enumerate_paths(nxt, nv, sink, path, res) path.pop() # 回溯，别忘了这一句 return res

调用enumerate_paths(nxt, stages[0][0], stages[-1][0])，就能把所有最优路径一次性列出来。上面那道例题会返回两条：

[1, 2, 7, 10, 12] [1, 3, 6, 10, 12]

这里有个容易忽略的细节：path.pop()必须写，否则你会在同一条递归链上不断累积不同分支的顶点，输出一堆杂乱的超长序列。这个坑不在算法本身，而在回溯模板的书写习惯上，写错了非常难查，因为结果看起来"像是对的路径但多了几个点"。

提示：如果最短路数量可能爆炸（某些图的并列决策能组合出指数级条数），先跟出题人确认是否真的需要全部输出，必要时改成"只输出条数"或"输出字典序最小的一条"。

5. 我踩过的四个坑：段序、INF、多解与孤立顶点

5.1 顶点编号不等于段序：最隐蔽的一类错

最坑的一次经历是这样的：题目给的图顶点编号是 1 到 12，我下意识以为"编号小的在前面的段"，于是循环写成for u in range(n-1, 0, -1)，按编号从大到小推。跑出来的小样例看着没问题，因为那个样例恰好编号顺序和段顺序一致；换一个编号打乱的测试数据，直接输出错误答案。顶点编号和阶段编号没有任何必然联系，编号只是标识符，段才是拓扑结构。

正确做法是显式维护 stages 列表，所有循环都基于 stages 展开，绝不基于顶点编号做假设。如果题目只给图和边、不给段划分，那就先做一次拓扑排序：每个顶点的层级等于所有入边起点的最大层级加 1。这一步做完，段划分就唯一确定了（允许存在空段），后续才能安心递推。我在写代码时习惯先把 stages 打印出来，人工扫一眼每段的顶点数量和编号，确认无误再往下写，这两分钟能省掉半小时的 debug。

5.2 INF加法与溢出：Python之外的语言必须当心

Python 里float('inf') + 5还是inf，太省心了，所以我以前写 C 版本的作业时直接照搬INF = 1e9，然后写cand = w + cost[v]。当 cost[v] 是 1e9 的时候，加上一个几万权值的边，结果就是 1000000xxx，仍然远大于任何合法距离，不会误选。但如果 INF 取的是INT_MAX（约 21 亿），加上边权就直接溢出成负数，然后这个负数比所有合法路径都小，被 min 选中，最后输出一个负的最短距离，看上去像是"图里有负权边"。

规避办法有两个：一是 INF 取一个安全的大值，比如10**9或者"所有边权之和 + 1"，保证它加上任何边权都不会溢出；二是在加法之前先判断if cost[v] == INF: continue。我更推荐第二种，逻辑上最干净，也顺手处理了不可达顶点的问题。Java 里还可以用long存距离，但治标不治本，判断不可达才是正解。

5.3 多解覆盖：为什么你的程序只输出了一条路

前面反复强调过，这里再完整走一遍错误现场。假设你写的是：

if cand < cost[u]: cost[u] = cand nxt[u] = v

顶点 1 在计算时，先遍历到走 2 得到 16，写入 nxt[1] = 2；再遍历到走 3 也得到 16，因为不满足"小于"，所以不更新。最终 nxt[1] 只剩下 2，输出的路径只有一条。如果你压根没意识到有第二条，这个 bug 会一直潜伏到老师批改时才暴露。

修复就是加一个elif cand == best: nxt[u].append(v)，并且把 nxt 从整数数组改成列表数组。改动很小，但要求你在写第一版代码时就意识到"多解"这件事的存在。一个经验判断：只要题目里出现"输出所有最短路径"或者"最短路径有多少条"，决策数组就必须是列表。哪怕题目没明说，养成列表的习惯也不吃亏，顶多多两次 append。

5.4 中间段有顶点不可达时该不该保留

还有一种情况值得单独说：某个中间段的顶点所有出边都通向"死路"（比如它通向的顶点本身无法到达汇点），那它的 cost 会一直是 INF。这时上一段在比较候选值时，w + INF显然不会被选为最优，所以算法结果不受影响。但如果题目要求判断"是否存在从源点到汇点的路径"，你就需要在最后检查 cost[源点] 是否仍是 INF。

关于孤立顶点要不要从 stages 里剔除，我的建议是保留但标记。剔除会让段结构错乱，影响手动核对；保留的话，它自然会被 INF 排除，代价只是多一次无效遍历。真正要小心的是"某个段整体不可达"的极端情况，这时整段都是 INF，属于题目本身无解，应该在输出层给出明确提示，而不是打印一个 inf 数字了事。

6. 多段图DP的三种变形与选型边界

6.1 求最长路径：只有DAG才敢这么做

一般图上的最长路径是 NP 难的（因为要判断有没有正环），但在多段图这种 DAG 上，最长路径反而和最短路径是一对孪生兄弟，只要把 min 换成 max 就完事：

longest[i] = max{ w(i, j) + longest[j] }

边界依然是longest[汇点] = 0。为什么这里可以随便取 max 而不用担心死循环？还是因为无环——所有子问题都指向"更靠后"的段，依赖关系严格递减，永远推不回来。这一点在做"资源最大化""收益最大化"这类题的时候特别有用，比如项目排期里每个阶段选一个方案，要求总收益最大，本质就是多段图最长路径。

不过要小心一点：如果图里存在不可达的顶点，max 版本会更危险，因为 INF 参与 max 会直接污染结果。所以做最长路时，遇到不可达顶点必须显式跳过，不能参与比较。我通常会用一个单独的布尔数组标记可达性，或者干脆把不可达顶点的值设成-INF再取 max。

6.2 最短路径计数与"第k短路"

在决策收集的基础上，路径条数就是一个很自然的扩展：设cnt[i]表示从 i 出发到汇点的最短路径条数，则

cnt[i] = sum{ cnt[j] } ，对所有满足 w(i,j) + cost[j] == cost[i] 的 j

边界cnt[汇点] = 1。这样一遍 DP 下来，cnt[源点]就是所有最短路的条数，不需要真的把每条路径都展开，避免了指数级枚举。这个技巧在笔试里挺常见，遇到"最短路径有多少条"直接上计数 DP，比 DFS 枚举稳得多。

至于第 k 短路，做法就复杂一些了，通常要维护每个顶点的 k 个候选值（也就是把 cost 从标量升维成大小为 k 的小根堆），逐段合并。多段图的结构能把它压到 O(k·(V+E)·log k) 左右，比一般的 Yen 算法友善不少。这块属于进阶内容，期末题基本不会考，但了解一下思路没坏处。

6.3 什么时候该放弃多段图DP，改用通用最短路

用顺了这个套路之后，容易产生"什么都想套多段图"的冲动。以下三种情况要果断换方案：

简单总结成一句话：多段图 DP 的核心竞争力来自"无环 + 分段"这两个结构性质，一旦结构被破坏，就得回到通用最短路工具。反过来说，只要你确认了这两个性质，就别去堆优化了，一段双层循环就是最优解，复杂度 O(V+E)，比朴素 Dijkstra 的 O(V²) 还快。

再补一个实际经验：很多在线判题系统会给出顶点数上限，比如 n ≤ 1000、m ≤ 10000。看到这个量级，如果你的代码是 O(V²) 的矩阵遍历，勉强能过但很悬；如果按段遍历邻接表，跑起来连时间都感知不到。所以即使题目名字里写着"动态规划"，也别忘了把数据结构选对，这两件事从来不是分开的。

我在实际做题和教学里发现，这道题真正难的地方从来不是递推公式——那个公式看一遍就记住了——而是阶段划分的正确性、决策数组的多解处理、以及不可达状态的边界判定这三件事。公式所有人都能默写，能把边界写干净、把并列解一个不漏地吐出来的人，才是真正把这道题吃透了。下次再遇到"多段图最短路径"，先别急着敲代码，画个表把 stages 列出来，按段倒着填一遍，剩下的就只是翻译工作。