最短路在算法竞赛里属于那种“人人都说入门简单却几乎人人都在中档题翻过车”的模块。模板确实就那几个堆优化Dijkstra、朴素Bellman-Ford、SPFA、Floyd-Warshall背下来在裸题上拿分不难但你去看任何一场正式的算法竞赛最短路几乎从来不裸奔。它要么披着“最小花费”“最低电量”“最大通信延迟”的外衣要么直接把建图这一步藏进题意里让你读完题完全看不出这跟路有什么关系。这篇文章我想从一个刷题老手的角度把最短路这条线完整梳理一遍从四套基础算法的原理和适用边界到一条由易到难的刷题路线再到次短路、分层图、差分约束这些拓展变形最后把我这些年反复踩过的坑和换来的经验一次性倒出来。无论你是刚学完图论基础、想开始刷最短路的入门选手还是已经会写模板、卡在中档建模题的进阶选手都能在这篇整理里找到对应的内容。1. 最短路问题的本质与四大基础算法扫盲1.1 把“单源、多源、负权、负环”这几个概念先锤实先别急着背代码。最短路题一错百分之八十是概念边界没理清。最短路定义本身很简单给定一张图每条边有个权值从点s到点t的一条路径边权和最小就是最短路。但题目里经常出现四个定语直接把算法选择给限死了。单源最短路只有一个起点s求它到其余所有点的最短路。典型算法是Dijkstra和Bellman-Ford系列。多源最短路不做任何假设。负权边边权存在负数。一旦出现负权边Dijkstra的贪心前提就被打破了必须换Bellman-Ford或者SPFA。负环图中存在一个环环上边权和为负。这是最短路里最阴间的存在因为只要存在负环最短路就“无定义”——你可以沿着负环无限绕圈路径长度持续缩小没有下限。你可以拿生活场景类比边权是“花销”正权边是正常消费负权边是“倒贴钱”的买卖。如果有个环路越走越赚那所有人都可以无限套娃下去自然不存在什么最优路线。还有一个容易忽略的点有向图和无向图的最短路在实现上差异很大。无向图每条边要建成两条有向边遇到重边、自环也要提前想清楚怎么处理。很多入门选手第一次做无向图题WA不是算法错了而是加边函数只加了一条。1.2 四种算法怎么选用一张表看懂算法时间复杂度能否处理负权负环判断适用场景堆优化DijkstraO((NM)log N)不能不能边权非负的单源最短路绝大多数题目的默认选择Bellman-FordO(NM)能能边权有负、且数据范围很小N、M都在几千内SPFA平均接近O(M)最坏O(NM)能能有负权边时优先考虑但会被刻意构造的数据卡到TLEFloyd-WarshallO(N^3)能非负环不明显N≤500左右的多源最短路或需要维护任意两点距离这个表格是无数人总结过的结论但我还是要强调背后的原因。Dijkstra能跑得快依赖一个贪心性质每次从堆里取出的最小dis在非负边权下已经是最终答案不会再被更新。负权边会破坏这一点因为这个“最小”可能后续还会被更小的值修正。Bellman-Ford则完全不赌运气它做N-1轮全边松弛本质是对“最短路最多经过N-1条边”这一事实的暴力验证。SPFA是Bellman-Ford的队列优化随机图上表现好但最坏情况确实能被卡成O(NM)。Floyd则是动态规划枚举中转点k来逐步逼近任意两点最短路。1.3 三份核心模板代码背之前先理解每行堆优化Dijkstra是重中之重建议默写。#include bits/stdc.h using namespace std; using ll long long; const int N 2e5 5; const ll INF 0x3f3f3f3f3f3f3f3f; vectorpairint, ll g[N]; ll dis[N]; bool vis[N]; void dijkstra(int s) { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dis[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto [v, w] : g[u]) { if (dis[v] dis[u] w) { dis[v] dis[u] w; pq.push({dis[v], v}); } } } }关键就一行if (dis[v] dis[u] w)这叫松弛操作。它的含义是“如果经过u再到v比当前记录的dis[v]更短就更新”。所有最短路算法本质上都在反复做这件事区别只是松弛的顺序和次数。Bellman-Ford的模板更朴素bool bellman_ford(int s, int n) { memset(dis, 0x3f, sizeof(dis)); dis[s] 0; bool updated; for (int i 1; i n - 1; i) { updated false; for (int u 1; u n; u) for (auto [v, w] : g[u]) if (dis[v] dis[u] w) { dis[v] dis[u] w; updated true; } if (!updated) break; // 已经收敛可以提前退出 } // 再跑一轮若还能松弛说明存在负环 for (int u 1; u n; u) for (auto [v, w] : g[u]) if (dis[v] dis[u] w) return false; return true; }Floyd则是三重循环但注意中转点k必须放在最外层ll f[N][N]; void floyd(int n) { for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (f[i][j] f[i][k] f[k][j]) f[i][j] f[i][k] f[k][j]; }为什么k放在外层因为Floyd的实质是逐步允许“前k个点作为中转点”如果你把i、j放外层k内层那么某些路径可能用了还没允许的中转点结果就不对了。这个细节在“灾后重建”这类动态加点题里特别有用后面会说。2. 从模板题到经典应用题的刷题路线2.1 第一梯队先把模板敲到“肌肉记忆”我先说结论模板题不刷够三到五道后面建图题会写得极其痛苦。因为建图题的难点在建图逻辑如果算法部分还要边想边查脑子根本腾不出来。第一梯队我推荐这几道洛谷P4779【模板】单源最短路径标准版这题直接用堆优化Dijkstra写。为什么选标准版而不是弱化版因为标准版专门卡SPFA能逼着你写真正的堆优化Dijkstra。很多人初学用弱化版SPFA过了以为自己会了结果一上标准版就被卡得怀疑人生。这才是好事卡一次就记住了。洛谷P1629 邮递员送信题意是一个邮递员从1号点出发分别到2到n号点送信再回1号点求总路程。这题的正解是正向图跑一遍最短路再把所有边反向从1号点再跑一遍最短路。前者是“1到所有点的距离”后者是“所有点到1的距离”。第一次接触“反向建图”这个概念强烈推荐做。洛谷P1144 最短路计数在Dijkstra过程中统计最短路条数取模。代码只比模板多了几行但涉及一个很隐蔽的问题什么时候更新cnt数组、什么时候累加。我后面在拓展章节会专门讲先做一遍感受一下。洛谷P1828 香甜的黄油有若干头牛分布在不同的牧场牧师要去一个牧场让所有牛都过来求所有牛到该牧场的最短路之和的最小值。数据范围小可以直接枚举每个牧场作为终点分别跑Dijkstra取总和最小。这道题让我明白了“最短路经常不是终点只是解决更大问题的工具”。第一梯队的验收标准很简单不看任何资料15分钟内写出堆优化Dijkstra并一次AC。没达到就别急着往下刷多写几遍。2.2 第二梯队学会从题目里“挖图”裸模板题解决了真正的挑战来了题目里根本没有“图”或者图需要你自己构造。第二梯队这几道题每一道都代表一种常见建模套路。洛谷P1119 灾后重建这题妙在村庄按时间依次修复询问时只允许使用已修复的点作为中转。乍一看图是静态的但答案要求的是动态的任意两点最短路。正解是在Floyd的每一轮更新中把新修复的村庄当作中转点k加进去。做完这题你对Floyd的k循环顺序会理解到骨子里。洛谷P1462 通往奥格瑞玛的道路这题把二分答案和最短路结合。题目要求最小化“路径上最大点权”同时保证路径边权和不超过一定血量。做法是二分最大点权把点权超过mid的点都禁掉看是否存在一条1到n的边权和不超过血量的路。最短路经常被嵌套在二分判定里这几乎是中档题的标配。洛谷P1948 电话线一条从1到n的路径可以选至多k条边免费最小化剩余边的最大值。经典解法有两种一种是二分答案把大于mid的边权设为1、小于等于mid的设为0跑01BFS或Dijkstra做判定另一种是直接分层图。建议两道解法都写一遍对比一下空间和代码量。洛谷P4568 飞行路线分层图最短路最经典的板子。题意是允许免费乘坐k次航线求最少花费。建图方式是把一张原图复制成k1层第i层到第i1层有一条0权边表示“这里使用了一次免费机会”。这题跑完后你对“状态拆层”的理解会上一个大台阶。第二梯队的重点不是“算法多难”而是“为什么这样建图”。做题时请一定逼自己写出“我建出来的图里每个点代表什么、每条边代表什么、0权边又代表什么”这几句话写不出来说明还没真正理解。2.3 第三梯队中档进阶题开始接触建模这个梯队的题已经不能靠模板直接套了但也不至于难到完全没有方向适合作为下一阶段的主力。POJ 3255 / 洛谷P2865 Roadblocks次短路模板题。严格次短路的求法需要维护两个dis数组一个最短、一个次短转移时分类讨论。这题我强烈建议自己推一遍转移逻辑再写代码因为次短路的更新顺序很容易写错。Codeforces 567E President and Roads最短路边判定问题问每条有向边是否一定在从s到t的最短路上如果不在能否把边权减小使它成为最短路的一部分。解法依赖最短路树和tarjan求桥属于“最短路图论进阶知识”的组合题适合作为拓展。Codeforces 1196F K-th Path给出一张n个点m条边的无向图求全局第k小的简单路径长度k≤400。做法是先取边权最小的k条边把涉及到的点拿出来跑Floyd或任意两点最短路再把所有路径排序。这里面“用边数压缩状态”的思路很值得细品。洛谷P1993 小K的农场 / P3275 糖果差分约束系统的入门题。通过建边把不等式组转化成一个图然后用最短路或最长路判断可行性。这属于“最短路思想反哺数学建模”的典型代表放第三梯队是因为建图思维跨度大初学者往往想不到。这个梯队不用急着全做完挑两三道有代表性的先消化剩下的留到拓展阶段配合专项练习。3. 拓展题型的六大变形方向3.1 次短路与K短路从一条路到前K条路为什么次短路值得单独说因为它几乎是所有“最短路扩展”里最容易上手的也是很多中档题的代码模板来源。严格次短路的朴素想法是把最短路上的每条边删掉再跑一次最短路取最小值。但这个做法复杂度O(M * (NM)logN)绝大多数题目过不了。更主流的做法是双状态Dijkstrall dis1[N], dis2[N]; void dijkstra_second(int s) { memset(dis1, 0x3f, sizeof(dis1)); memset(dis2, 0x3f, sizeof(dis2)); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dis1[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (dis2[u] d) continue; // 比次短还大直接扔掉 for (auto [v, w] : g[u]) { ll nd d w; if (nd dis1[v]) { dis2[v] dis1[v]; dis1[v] nd; pq.push({nd, v}); } else if (nd dis1[v] nd dis2[v]) { dis2[v] nd; pq.push({nd, v}); } } } }注意几个细节更新最短时要把原来的最短路“降级”成次短如果nd等于dis1[v]直接跳过因为要求严格次短比次短还大的状态不用入堆。再往上走是K短路常用A*算法先反向建图求出终点t到所有点的最短路作为估价函数h(u)再从起点开始用优先队列按g(u)h(u)排序扩展。当终点第k次出队时该状态对应的路径长度就是第k短路。这个思路把“贪心”和“启发式搜索”结合得非常妙建议在掌握双向最短路之后再尝试。3.2 最短路计数与最短路树在图上做统计最短路计数看着简单实际上是个很容易出错的题。核心思想是最短路构成一张DAG——如果dis[v] dis[u] w那么u到v就是一条“最短路上的合法转移”。因为所有最短路的长度都不可能成环除非有0权环否则绕一圈只会变长所以我们可以在这个DAG上做DP。常见写法是直接在Dijkstra里更新cntif (dis[v] dis[u] w) { dis[v] dis[u] w; cnt[v] cnt[u]; pq.push({dis[v], v}); } else if (dis[v] dis[u] w) { cnt[v] (cnt[v] cnt[u]) % MOD; }但这里有个经典坑Dijkstra弹出u时cnt[u]不一定已经算完。因为可能有多条最短路径都能到达u而它们还没全部被处理完。稳妥做法是第一遍先跑Dijkstra得到所有dis第二遍把点按dis升序排序然后在最短路DAG上做DP按这个顺序累加cnt。这样能保证某个点的cnt被完整统计后再向后传播。最短路树是另一个概念把每个点起点除外记录它最短路上的前驱边就得到一棵树。这棵树很有用比如判断哪些边是单源最短路上的“必经边”先跑出最短路树再在原图中考察每条边是否满足dis[u] w dis[v]如果一条最短路边不在树里说明它不是唯一的。CF 567E就是这样做的再用tarjan求桥就能判断“删除这条边是否会让最短路变长”。3.3 分层图最短路把“免费次数”变成一维状态分层图最短路是我认为性价比最高的拓展技巧学一次能用很久。它的适用场景非常明确路径上允许做最多k次特殊操作每次操作会改变花费比如免费、打折、增加惩罚。最简单的建模方式是拆点把原图复制成k1层第i层表示“已经用了i次特殊操作”的状态。层内边保持原图边权层间加边权为0的“特殊操作转移边”方向从第i层到第i1层。以P4568飞行路线为例原图有n个点m条边允许k次免费。建图后总点数变成n*(k1)边数变成m*(k1)k条。编号可以用u * (k 1) i表示“第u个点、第i层”跑一遍堆优化Dijkstra答案就是min(dis[t * (k1) i], i0..k)。这里有个实用细节很多题目数据范围看起来不小k可能到10或20建完层后节点数突增数组一定要开够否则越界的bug极难排查。除了展开建图也可以用“状态扩展式Dijkstra”不真正建图而是在转移时增加一个维度的判断。两种写法各有优劣展开建图直观好调试状态扩展省内存但更容易写乱建议先学会展开再根据题目需要换写法。3.4 虚拟节点与反向建图用图论语言翻译题意虚拟源点/汇点是我见过最实用的建图技巧之一。题目说“有多个起点求这多个起点到某个终点的最短路”如果一个个起点跑复杂度是O(K * M logN)更好的做法是加一个超级源点S用0权边连到所有起点然后从S跑一次最短路。原理很好理解从S出发经过0权边进入某个起点后续路径完全等同于从该起点出发。反过来多个终点也可以建超级汇点把所有终点连到T边权0在反图上跑最短路。更进阶一点CF 1196F求全局第k小路径时就是取边权最小的k条边把涉及到的点作为候选起点/终点通过多次分组跑多源最短路来压缩复杂度。反向建图则是一个看多了才能想到的习惯。比如要求“所有点到某个点t的最短路”如果在正向图上跑要跑N次Dijkstra但建反图后从t跑一次得到的就是原图中所有点到t的最短路。很多图论题都需要“正反各跑一遍”比如次短路、必经边判断、多源多汇组合等P1629邮递员送信就是第一道让你建立这个习惯的题。3.5 状态压缩最短路当“到达”还远远不够普通最短路只关心“我在哪个点”但有些题目还要求“我带了哪些钥匙”“我收集了哪些物品”“我现在是哪种状态”。这类题目通常把状态压进dis数组的第二维甚至第三维。最典型的是钥匙收集型问题比如一个迷宫中有几种锁和对应的钥匙没有钥匙不能通过锁门。这里节点的状态可以定义为“持有的钥匙集合”也就是一个mask。定义dis[u][mask]为到达u点、钥匙集合为mask的最小步数用BFS或Dijkstra在nmask种状态上转移。状态总数点数2^钥匙种类数当点数不大时完全跑得动。这种题的关键在于“拆状态”的直觉把额外条件变成状态维度就能把一个看似玄学的题变成普通最短路。类似的还有“油箱容量型”问题把剩余油量作为状态有次数限制的问题把剩余次数作为状态。做多了你会发现分层图其实就是状态压缩的一个特例只是“状态维度”比较规整可以直接用拆层表达。3.6 差分约束系统用最短路解不等式组差分约束是“最短路思想反哺数学建模”的典型代表。它处理的是形如一组不等式x_u - x_v c判断是否存在解以及求一组可行解。建模方式非常固定把不等式看成一条边从v向u连一条权值为c的边。为什么因为最短路满足三角形不等式dis[u] dis[v] w稍微变形就是dis[u] - dis[v] w。所以如果原图有解跑最短路得到的dis就是一组可行解若存在负环则不等式组无解。对于x_u - x_v c可以两边乘-1变成x_v - x_u -c也可以直接建最长路。实际做题时我建议统一转成形式因为最短路的理解和调试都比最长路舒服。还要注意如果图不连通可能出现“某个不等式没有节点能约束到”的情况此时需要加一个超级源点向所有点连0权边同时把所有点初始化为0并入队保证所有点都能被松弛到。洛谷P1993小K的农场和P3275糖果都是很好的入门练习。糖果那题有个特殊坑如果数据很大要用SPFA判断正环需要把“入队次数”和“路径边数”两个概念分清否则会误判。4. 建图与状态设计拉开差距的关键4.1 图的存储邻接矩阵、vector邻接表和链式前向星选错存储方式在竞赛里真是会出人命的。邻接矩阵适用于N≤500、需要频繁查询任意两点边权的场景Floyd是它唯一的归宿。vector邻接表可读性最好几乎可以无脑用堆优化Dijkstra在N、M到2e5级别都扛得住。链式前向星在旧竞赛圈很流行写法是手写数组模拟链表优点是内存紧凑、常数小适合追求极致性能或者需要遍历“以u为起点的所有边”的题。链式前向星的加边模板int head[N], nxt[M], to[M], w[M], cnt; void add(int u, int v, int val) { to[cnt] v; w[cnt] val; nxt[cnt] head[u]; head[u] cnt; }遍历时for (int e head[u]; e; e nxt[e]) { int v to[e], val w[e]; // ... }我的建议是vector邻接表堆优化Dijkstra作为默认配置链式前向星作为备选技能。不用为了“显得专业”强行用链式前向星但如果某个题卡的常数非常狠链式前向星确实可能比vector快一截。4.2 虚拟节点到底该怎么连边虚拟节点的核心是“用一条0权边把多个真实节点合并成一个起点/终点”它不改变最短路的结果因为0权边不会被优先选择去“污染”答案。实际操作中有三类常见场景。第一多起点单终点超级源点连向所有起点边权0从超级源点跑Dijkstra。第二单起点多终点理论上可以先反向建图变成第一类但更直观的做法是建超级汇点所有终点连向超级汇点边权0从原起点跑Dijkstra答案就是到超级汇点的距离。第三判断某个边是否能成为“最早被打通”的边有些题要求“边权改为多大才能让最短路经过某条边”这时可以把要找的边拆成两段配合虚拟节点做二分判定。虚拟节点最需要注意的是方向别搞反以及0权边和负权边混用时别影响SPFA的负环判断。我见过有人把超级源点和所有点都连了0边结果SPFA把0边也当成“新增最短路”导致cnt数组误判负环。解决办法是只对真实起点连0边而不是所有点。4.3 拆点和拆边把点开成多维拆点是个思路不是具体算法。它的本质是“把原来一个点在不同状态下的行为分开建模”。最常见的例子是把一个点拆成入点u和出点u适合处理“通过这个点需要花费代价”的题比如点权转边权。具体做法原图每个点u拆成u_in和u_out内部连一条边权为点权的边从u_in到u_out原图中u到v的边变成u_out到v_in边权不变。这样一来标准的最短路算法就可以自动处理点权了。分层图也是拆点的特例把“第几层”当作一维同一个真实点在不同层的编号不同不同层之间用特殊边连接。还有状态压缩最短路其实也是把mask作为一维看作“拆出了2^k个状态点”。拆点时要注意节点数会成倍增长数组大小和循环上限都要同步修改。这是最短路题最常见的RE来源。我的经验是凡是涉及拆点的题先把新的点数算清楚标注在代码注释里再开数组别凭感觉。5. 实战中反复踩过的坑与处理经验5.1 SPFA不是默认算法知道什么时候该用它我看到太多入门选手把SPFA当万能模板因为代码短、随机图跑得快。但SPFA有一个致命弱点最坏情况可以被数据卡成O(NM)而且现在很多出题人故意卡。我的原则很简单没有负权边一律用堆优化Dijkstra。有负权边且N比较小用Bellman-Ford。有负权边且需要快速跑才考虑SPFA但要意识到存在被卡的风险。SPFA唯一不可替代的场景是需要判断负环的时候因为它能一边松弛一边盯“路径边数”。代码里判断负环的方式如下// cnt[v] 表示从源点到v的最短路经过的边数 if (dis[v] dis[u] w) { dis[v] dis[u] w; cnt[v] cnt[u] 1; if (cnt[v] n) return false; // 存在负环 if (!inq[v]) { q.push(v); inq[v] true; } }为什么是cnt[v] cnt[u] 1而不是“入队次数”因为入队次数只能说明一个点被重复松弛了很多次不一定能形成直观的证据而“路径边数超过n”则直接说明最短路径里出现了至少n1个点一定是有环而最短路算法收敛时不应该出现这种情况。养成用cnt判断负环的习惯比用“入队次数”更稳。5.2 INF选错直接WAint和long long的边界这绝对是我见过最频繁的WA原因之一。int类型下很多人喜欢写INF INT_MAX然后松弛时dis[u] w直接爆成负数导致判负环时误判、Dijkstra优先级队列乱套。正确做法是0x3f3f3f3f它约等于10^9数量级两个INF相加约2.12e9仍在int范围内。而且memset(dis, 0x3f, sizeof(dis))可以直接把它填进去。long long类型下用0x3f3f3f3f3f3f3f3f约4.6e18两个相加会超过LLONG_MAX约9.2e18 9.22e18? 实际上0x3f3f3f3f3f3f3f3f是4557430888798830399两倍9.1e18刚好在LLONG_MAX临界内所以安全。很多选手图省事写1e18但其实INF 8e18就会在加法时爆掉用1e18同样有风险。我的习惯是INF 0x3f3f3f3f3f3f3f3f并配合memset使用。另外只要做过带负权边或者计数类的题强烈建议全链路用long long。别省那点空间溢出一次查错的时间够你写十道题。5.3 堆优化Dijkstra的三个使用细节堆优化Dijkstra看似简单但细节决定成败。第一出堆时要判断vis[u]。因为同一个点可能被多次松弛、多次入堆出堆时如果不跳过已确定的陈旧状态会把复杂度从O((NM)logN)拉到O(MlogM)甚至产生错误结果。正确写法是出堆后if (vis[u]) continue; vis[u] true;。第二不要用更新后的dis[u]直接continue。有些写法会用if (d dis[u]) continue;代替vis数组这在大多数情况下也是对的但如果存在0权边可能反复处理。两种写法都行但我不建议混用容易糊涂。第三优先队列默认是大根堆必须传greater改成小根堆。很多人第一次写DijkstraWA就是因为忘了这个。另外注意pair的排序是先比较first再比较second用{距离, 节点编号}是最稳的。5.4 负环判断的两种落地写法负环不仅在差分约束中出现凡是SPFA、Bellman-Ford题目都可能涉及。我整理一下两种标准写法。Bellman-Ford的写法做N-1轮松弛后如果第N轮还能松弛则存在负环。代码见第一节模板。这个写法非常严谨理解成本低缺点是慢。SPFA的写法维护cnt数组记录最短路经过的边数当cnt[v] n时说明从源点到v的最短路包含了至少n条边也就是有n1个点必然存在环。如果这个环是负环那最短路会无限更新下去所以判定存在负环。注意如果你用“入队次数n”判断在有些特殊图比如大量0权边上可能会误报用“边数”更稳。还要注意一个方向性差分约束里如果用的是最长路那就判正环条件改成cnt[v] n即可。别把最短路的负环判断硬套到最长路上。6. 刷完这一路我对最短路最深的几点体会最短路刷到最后你会发现模板只是入场券真正的竞争力来自“把问题翻译成图”的能力。我个人的习惯是拿到一道题先强制自己回答三个问题点是什么边是什么要求什么如果答案模棱两可说明还没读懂题。比如“免费坐k次飞机”点就是“位置已用免费次数”边就是“航班”要求的就是从起点到终点“已用免费次数不超过k”的最小花费。这样一套翻译下来解法往往自己就浮出来了。另一个建议是把最短路当成“题库型”知识点来刷。今天刷一道分层图明天刷一道差分约束后天刷一道状态压缩比连续刷十道裸模板题有效得多。因为每个变形方向都对应一种建图范式范式见得多了考场上才能快速辨认。我当年学分层图花了很久就是因为只在P4568上练了一遍没有在别的题里复现。后来多做几道之后“可以用层数表示已用次数”这个范式才算真正内化。最后分享一个小技巧做最短路题时手边常备一张草稿纸把建图方案画出来。尤其是虚拟节点、拆点、分层这些操作画在纸上比在脑海里想清晰一百倍。很多WA其实是建图方向画反了画一遍就能看出来。最短路是个大坑但也是个入口。它通往二分判定、状态压缩、差分约束、网络流里的一大票高级内容。把这篇文章里的路线和坑走完一遍你会发现自己的建图直觉、边界意识、代码调试能力都上了一个台阶而这正是刷最短路最值钱的地方。