1. 先搞清楚什么场景需要“免费 k 条边”1.1 从一个最短路问题说起第一次见“分层图最短路”这个概念多半是因为这类题目给出一个 n 个点、m 条边的无向图每条边有边权现在你可以选择最多 k 条边让它们的边权变成 0然后求从起点 s 到终点 t 的最短路径花费。翻译成大白话就是给你 k 次“免费通行”的机会怎么走最划算。这种问题听起来很简单有人第一反应是先把原图跑一遍最短路然后把最短路径上最长的 k 条边免费掉不就行了吗我第一次也这么想但这个思路是有问题的。因为最短路径本身是固定的你只是在这条固定路径上挑边免费而真正的全局最优解完全可能为了把某条大边免费掉而绕一条更远的路。举个例子起点到终点有一条直达边权值是 100但你只有 1 次免费机会免费后花费 0另一条绕路路径由两条边组成权值分别是 60 和 60如果用 1 次免费总花费是 60。如果只看最短路直达边 100 是最短的但免费后是 0好像赢了可如果路径上最长的边不在最短路上呢换一组数据最短路是两条边 8090免费一条后是 80另一条绕路是 30100免费一条后是 30。这时只有把状态扩展成“用了几次免费走到哪个点”才能在所有路径里找到最优解。于是就有了分层图。1.2 把“用了多少次免费”变成图的一维状态分层图的核心思想并不复杂原本我们求最短路状态只有“当前在哪个点”。现在多了一个限制条件就是“已经免费了几条边”。那干脆把状态扩展成二维(用了几次免费, 当前在哪个点)。这个二维状态可以映射成一维处理把原图复制 k1 份编号为第 0 层、第 1 层、第 2 层……第 k 层。在第 i 层中所有图的结构和原图一样表示“已经免费了 i 条边”的情况下当前所在的顶点。层与层之间通过“免费边”连接如果你在点 u想通过一条边 (u, v, w) 走到 v并且决定在这条边上使用一次免费机会那么就从第 i 层的 u 跳到第 i1 层的 v花费为 0。如果不想用免费机会就继续在同一层的 u 走到同一层的 v花费为 w。这样一来从第 0 层的起点出发跑到第 0 层到第 k 层任意一层的终点最小花费就是答案。因为最短路算法会自动帮我们决定在哪些边上使用免费机会也能保证总共用的次数不超过 k。我一开始学的时候总觉得分层图很抽象后来用了一个生活化的类比想象你开了个游戏里面有 k1 张一模一样的地图副本每张地图代表你当前还有几次“免死金牌”。你在第 0 层地图里正常走路当你用掉一次免费机会时就按一下切换按钮直接传送到下一张地图的同一个位置传送本身就是瞬间的边权为 0如果你不用机会就在当前地图里继续走。你需要找到一条从第 0 层起点到达任意一层终点的最短路。这样理解起来就会顺很多。2. 分层图的两种建图方式我建议你掌握第二种2.1 显式建图把所有层都建出来第一种实现方式是直接把 k1 层图“摊平”成一个点数量为(k1) * n的大图。原来的点 u 在第 i 层对应编号i * n u。建图的时候对原图的每一条边(u, v, w)做两个操作层内边i * n u - i * n v权值为 w反向同理跨层边i * n u - (i1) * n v权值为 0反向同理从i * n v - (i1) * n u权值为 0。这里的跨层边就表示“在这条边上使用一次免费机会”。注意跨层边是单向的因为免费机会用掉之后不会倒流不能再从第 i1 层回到第 i 层。显式建图写完就直接跑一遍堆优化的 Dijkstra。起点是第 0 层的 s终点是任意层的 t答案取min(dist[i * n t])。这种写法的优点是直白新手不容易错缺点是内存开销大边数会成倍增长。一个简单的估算假设原图 m 条边建 k1 层后层内边有(k1) * 2m无向边每条算两条跨层边有k * 2m条总边数大概是(2k1) * 2m。如果 m 是 1e5k 是 10那总边数就是 420 万条左右虽然还能受得住但写起来要小心数组大小。2.2 隐式建图把层数写进 dist 数组我更推荐第二种写法尤其是参加比赛或者刷题的时候不建多层图而是在 Dijkstra 的堆节点里多存一个维度used表示已经免费了几条边。dist[u][used]表示走到点 u、已经免费了 used 条边的最小花费。转移分两种情况不使用免费机会走边(u, v, w)dist[v][used] min(dist[v][used], dist[u][used] w)使用免费机会走同一条边如果used k那么dist[v][used1] min(dist[v][used1], dist[u][used])这种写法不需要显式地开 k1 倍的点和边只需要在堆里多携带一个used代码量和内存都更优。实际写起来只是 Dijkstra 的内层循环里多了一个分支本质上和显式分层图是完全等价的。我个人的习惯是如果题目 k 很小比如 k10而且边数不大用显式建图方便调试如果 k 可能到 100 甚至更大或者边数很密必须用隐式写法。隐式写法也更能体现建模的本质——所谓分层图其实就是把“使用免费次数”这个限制变成图状态的一部分。2.3 显式建图的 C 参考代码分享一下我常用的显式建图模板。假设点编号从 1 开始n个点m条无向边k次免费机会起点s终点t。#include bits/stdc.h using namespace std; using PII pairint, int; const int N 110000; // 最大点数 const int M 2500000; // 边数上限 int head[N], nxt[M], to[M], w[M], tot; int dist[N]; bool vis[N]; int n, m, k, s, t; void addEdge(int u, int v, int cost) { to[tot] v; w[tot] cost; nxt[tot] head[u]; head[u] tot; } int nodeId(int level, int u) { return level * (n 1) u; // 让每层起点错开 } void dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[nodeId(0, s)] 0; priority_queuePII, vectorPII, greaterPII pq; pq.push({0, nodeId(0, s)}); while (!pq.empty()) { auto [d, id] pq.top(); pq.pop(); if (vis[id]) continue; vis[id] 1; int level id / (n 1); int u id % (n 1); for (int e head[u]; e; e nxt[e]) { int v to[e]; // 层内转移 if (!vis[nodeId(level, v)] d w[e] dist[nodeId(level, v)]) { dist[nodeId(level, v)] d w[e]; pq.push({dist[nodeId(level, v)], nodeId(level, v)}); } // 跨层免费边转移 if (level k !vis[nodeId(level 1, v)] d dist[nodeId(level 1, v)]) { dist[nodeId(level 1, v)] d; pq.push({dist[nodeId(level 1, v)], nodeId(level 1, v)}); } } } } int main() { scanf(%d%d%d, n, m, k); scanf(%d%d, s, t); for (int i 0; i m; i) { int u, v, c; scanf(%d%d%d, u, v, c); // 无向图层内要双向 addEdge(u, v, c); addEdge(v, u, c); } dijkstra(); int ans INT_MAX; for (int i 0; i k; i) { ans min(ans, dist[nodeId(i, t)]); } printf(%d\n, ans); return 0; }这里注意nodeId我用level * (n 1) u而不是level * n u是为了避免点编号从 1 开始导致的“0 号点与第 1 层起点冲突”的问题。宁可多开一点空间也不要在这种细节上翻车。2.4 数组大小怎么算才保险很多新人写分层图最头疼的就是数组越界。显式建图时点的数量是(k1) * n边数要仔细算。如果原图是无向图每条无向边对应两条有向边分层后每个原节点会出现在 k1 层里所以层内边总数(k1) * 2m。跨层边每两层的对应节点之间都要连一条有权边吗注意我们只需要对原图中的每条有向边建一条跨层边因为“免费”这个过程是在某条具体边上发生的。无向边的两端都能成为免费方向所以每条无向边会产生 2 条跨层有向边跨层总数为k * 2m。总的链式前向星边数组大小建议开2 * ( (k1) * 2m k * 2m )以上也就是(4k2) * m左右再乘个保险系数 2防止重边、手滑加反向边导致数组越界。我见过不少人开小数组导致莫名其妙的 TLE/RE如果是比赛环境建议直接开大的静态数组不要为了省内存而抠空间。如果题目保证 k 很小比如 k10那总边数也就在40*m级别开2000000到5000000通常够了。当然最稳妥的方式还是用 vector 的动态数组自动扩容省去手工算大小的烦恼。3. 隐式分层 Dijkstra代码更短思路更清晰3.1 为什么第二维写在堆里而不是建图里显式建图虽然好理解但代码写起来很容易出错层数多了后nodeId计算、跨层边的方向、无向边的双向性任何一个地方弄错答案都错得离谱。而且如果你想用dist[level][u]做状态显式建图还得维护一个从“节点编号”反推层数的过程。隐式写法把状态(level, u)直接放在堆里遍历边的时候现场判断走普通边还是免费边省掉了大部分建边操作。这种写法的另一个好处是如果题目要求每条边在不同情况下的免费规则不同你可以在转移函数里灵活处理不用改图的结构。3.2 堆节点要存三元组用 C 写隐式分层时堆里要存三个信息当前距离d、当前点u、已用免费次数used。可以自定义结构体也可以用tuple但注意 priority_queue 默认是大顶堆比较规则要反过来。我一般定义一个结构体然后重载大于号struct State { int d, u, used; bool operator(const State other) const { return d other.d; } };然后 Dijkstra 的主循环while (!pq.empty()) { State cur pq.top(); pq.pop(); int d cur.d, u cur.u, used cur.used; if (vis[u][used]) continue; vis[u][used] 1; for (auto [v, w] : g[u]) { // 不用免费 if (d w dist[v][used]) { dist[v][used] d w; pq.push({dist[v][used], v, used}); } // 用免费 if (used k d dist[v][used 1]) { dist[v][used 1] d; pq.push({dist[v][used 1], v, used 1}); } } }vis也可以不开因为 Dijkstra 保证每个状态第一次出堆时就是最优但为了常数优化通常还是开一个bool vis[k1][n1]。要注意dist数组的维度顺序我习惯把层数放在第一维因为层数一般比较小内存访问更连续。3.3 Python 版本十几行就能写完如果你用 Python 刷题分层图最短路也很清晰核心代码大概是import heapq def solve(n, m, k, s, t, edges): g [[] for _ in range(n)] for u, v, w in edges: g[u].append((v, w)) g[v].append((u, w)) INF 10**18 dist [[INF] * n for _ in range(k 1)] dist[0][s] 0 pq [(0, s, 0)] # (花费, 当前点, 已用免费次数) while pq: d, u, used heapq.heappop(pq) if d dist[used][u]: continue for v, w in g[u]: # 不用免费机会 if d w dist[used][v]: dist[used][v] d w heapq.heappush(pq, (dist[used][v], v, used)) # 使用免费机会 if used k and d dist[used 1][v]: dist[used 1][v] d heapq.heappush(pq, (dist[used 1][v], v, used 1)) ans min(dist[i][t] for i in range(k 1)) return ans这段代码和显式建图的答案完全一致。可以说隐式分层就是把“跨层边”的建立从预处理转移到了搜索过程中逻辑上更贴近“状态转移”的本质。3.4 复杂度分析这个算法快不快分层图跑 Dijkstra 的复杂度很好算状态数是(k1) * n每个状态会遍历它的所有邻边所以总边数相当于(k1) * 2m堆优化 Dijkstra 的复杂度是O((k1) * (n m) * log((k1)*n))。k 一般不会太大如果 k10这个复杂度大概是O(11 * (nm) * log(11n))比普通 Dijkstra 多了一个常数 11运行时间大概率还扛得住。如果 k 特别大比如 k1e5那就算法就退化成O(k*m)直接爆炸。这时候需要考虑别的思路比如这个题能不能用“二分答案 0-1 BFS”或者用费用流等高级算法。所以看到题目先看数据范围k 小优先分层图k 大另寻出路。4. 真实题目套路怎么把各种变式翻译成分层图4.1 免费 k 条边答案取所有层的最小值最经典的原型题就是“飞行路线”。题目大意给出 n 个城市m 条航线你可以免费乘坐最多 k 次航班求从 s 到 t 的最小花费。这就是分层图最短路的标准裸题直接套模板就能过。需要注意的只是 k 可能等于 0这时候退化成普通 Dijkstra。我做过很多次这题每次写完都要记着答案不能只取dist[k][t]因为可能不需要用完 k 次免费就已经到终点了。比如 k5但最短路总共有 3 条边免费 2 条后已经到终点剩下的 3 次不用白不用状态停在used2那层。所以最终答案必须遍历所有层取 min。4.2 变式免费机会不是全局的而是“每条边只能用一次免费”有些题会再加一个限制每条边被免费一次之后如果再次经过还得原价。这个就需要注意分层图里“跨层边只走一次”的语义。在显式分层图里跨层边只有从第 i 层到第 i1 层而且每条原边只建一条跨层边所以天然不会重复免费同一条边——因为一旦到了下一层你不可能再回到上一层用这条边的免费机会。但如果你写的是隐式写法就一定要保证“只有从低层到高层的转移才会触发免费”不能写反。4.3 变式删 k 条边后的最小直径 / 最小最大边权有一类题是这样的你可以删掉最多 k 条边然后求从 s 到 t 的路径上“剩余边权最大值最小是多少”。这和“免费 k 条边”其实是一样的思想只不过目标函数不是总和而是最大值。这种题如果你直接套分层图最短路dist 里存的是路径上的最大边权而不是边权和依然可以用 Dijkstra 做转移时max(current_max, w)。但如果 k 比较大还可以用二分答案二分一个答案 mid把边权大于 mid 的边看作“需要免费”的边代价为 1把边权小于等于 mid 的边看作“不需要免费”的边代价为 0然后跑 0-1 BFS 求从 s 到 t 的最小免费次数如果该次数 k则 mid 可行。这就是“Telephone Lines”那道经典题的套路。分层图和二分答案都能解但思路各有侧重。当你看到“最大值最小”这类字眼要立刻想到二分答案看到“最多 k 次免费、总花费最小”优先分层图。4.4 什么时候分层图不适用分层图也不是万能的。如果免费规则和“路径选择”耦合得很深比如“免费边必须连续使用”“免费边不能超过连续两条”那么单纯给层数加一维就不够了可能需要记录更多状态比如“当前连续免了几条边”。当状态数膨胀到无法承受时就要考虑动态规划、网络流或者其他建模方式。此外如果 k 很大、n 和 m 也很大分层图状态数(k1)*n会超出内存或时间限制。这时要思考是否可以使用“最短路 可撤销贪心”之类的技巧但那是另一个更进阶的课题了。新手阶段先把 k 不大的分层图吃透就够应付大部分面试和算法竞赛入门题了。5. 避坑指南这些坑我踩过一次就长记性了5.1 答案忘取所有层的最小值这个坑我在前面反复强调因为它太容易犯了。很多初学者包括几年前的我自己写完后直接输出dist[k][t]结果样例过不了。想一下如果起点就是终点st答案应该是 0但如果你强制必须用 k 次免费状态dist[k][t]可能根本不可达。所以记住输出min(dist[i][t] for i in range(k1))。5.2 无向图的免费边漏建反向显式建图时如果原图是无向边层内边要建两条u-v 和 v-u。跨层免费边也要建两条从第 i 层 u 到第 i1 层 v以及从第 i 层 v 到第 i1 层 u。漏掉任意一条都会导致某条边的免费方向失效。我见过有人只从 u 到 v 建了免费边然后从 v 出发想用免费走到 u 就永远走不到结果答案比标准答案大很多。排查这个坑可以把 k 设成 0跑普通 Dijkstra 跟标准答案对比如果能过再开 k 分层慢慢检查。5.3 Dijkstra 的vis标记不能只按点标记普通 Dijkstra 里vis[u]可以表示点 u 的最短路已经确定但分层图里状态是(used, u)同样的点 u在不同层的最短路是不同的。如果你只开一维vis会导致某一层的 u 被标记后其他层的 u 无法再入队结果就错了。所以vis必须是二维的vis[used][u]。用dist[used][u]判断跳过也是同理必须带上 used 维度。我在写隐式版本时也有一次手滑把if (dist[used][u] ! d) continue;写成了if (dist[u] ! d) continue;编译能通过但是运行结果一塌糊涂。这种低级错误只能靠细心和测试来防。5.4 重边、自环的处理分层图对重边和自环的处理和普通最短路一样如果有重边保留最小权值即可如果不处理只是多几条等价边也不会错只是慢一点。自环可能会造成无意义的层内转移但并不会导致答案错误因为在最短路算法中从 u 到 u 的权值非负不可能让距离变小。所以自环可以不管但如果你追求性能可以在建图时直接跳过 uv 的边。5.5 数据范围爆 int分层图会把状态数扩大 k1 倍最短路累计的边权和也可能超过 int 范围。尤其是当边权很大、路径很长时dist 一定要用 long long。如果题目给出的边权上限是 1e9路径长度最多 1e5那么路径和是 1e14int 肯定装不下。C 中memset(dist, 0x3f, sizeof(dist))的 0x3f3f3f3f 约等于 1e9对 long long 来说不够大建议用memset(dist, 0x3f, sizeof(dist))再配合 long long 时初始化为0x3f3f3f3f3f3f3f3f或者使用const long long INF 1e18;然后手动 fill。这个细节决定你是否会因为答案溢出而 WA。6. 进阶思考分层图还能用于哪些场景6.1 把“操作次数”编码成状态的思想可推广分层图最短路的核心是把“做了多少次特殊操作”这个额外信息编码到图的状态里。这个思想远远不只用于“免费 k 条边”。比如有 k 次机会把一条边的边权减半求最短路有 k 次机会瞬移无视边权求最短路有 k 次机会让路径上某段变为 0求最短路。这些都可以用同一种建模方式把操作次数作为一种维度层内转移表示不做操作跨层转移表示做一次操作。操作的影响权值归零/减半/瞬移体现在跨层边的权值上。我在学习图论后期甚至把一些动态规划的题也转成这种“分层跑最短路”的模型。比如一个常见的 DP 状态是dp[i][j]表示到了第 i 个点、已经用了 j 次某种技能的最小代价如果转移只依赖上一层/同一层的最小值那本质上就是一个带层数状态的隐式图最短路问题。6.2 分层图和其他图算法的结合分层图不仅可以配合 Dijkstra也可以配合 SPFA、0-1 BFS、A* 等算法。如果边权只有 0 或 1跨层边权为 0同层普通边权为 1那么可以直接用双端队列 BFS 跑每一层复杂度为O((k1)*(nm))比堆优化 Dijkstra 还快一个 log。在“Telephone Lines”这类二分答案题中0-1 BFS 加二分往往是时间最稳的写法。另外如果图中有负权边但不能有负环也可以用分层图 Bellman-Ford 或 SPFA 解决。只是算法竞赛里出现负权边的大多数场景结合“免费 k 条边”就变得比较棘手我建议优先考虑转化为非负权图或者直接用 SPFA 试一下但数据强不保证能过。6.3 从“分层图”到“多维状态最短路”的思维跃迁当你理解了分层图以后再看一些高级题目会豁然开朗。比如某些题目里不仅要考虑“免费次数”还要考虑“剩余油量”“携物重量”“状态压缩的集合”这些其实都是在把更多的状态维度塞进图里然后用最短路算法去搜。所谓“建图”不只是点和边也包括“状态”和“状态转移”。分层图是这类思维最小的一个入口。我自己刷题的时候遇到一个跟“次数限制”有关的图论题模版一般就是明确有哪些维度会影响决策免费次数、特殊标记等把这些维度作为状态的一部分设计dist[维度1][维度2]... [点]写出所有合法转移包括维度加一的转移跑 Dijkstra / BFS答案取所有合法终态的最小值。这套流程熟练之后再看分层图就不仅仅是记住一个算法而是一种建模方法。7. 一份可以直接抄的隐式建图模板总结最后我把最常用的隐式建图模板整理一个完备版包含输入输出、答案处理和小优化方便你直接粘去用。#include bits/stdc.h using namespace std; using ll long long; const ll INF 0x3f3f3f3f3f3f3f3f; struct Edge { int to; ll w; }; struct State { ll d; int u, used; bool operator(const State other) const { return d other.d; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k, s, t; cin n m k s t; vectorvectorEdge g(n); for (int i 0; i m; i) { int u, v; ll w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorvectorll dist(k 1, vectorll(n, INF)); vectorvectorchar vis(k 1, vectorchar(n, 0)); dist[0][s] 0; priority_queueState, vectorState, greaterState pq; pq.push({0, s, 0}); while (!pq.empty()) { State cur pq.top(); pq.pop(); ll d cur.d; int u cur.u; int used cur.used; if (vis[used][u]) continue; vis[used][u] 1; for (auto e : g[u]) { int v e.to; ll w e.w; if (!vis[used][v] d w dist[used][v]) { dist[used][v] d w; pq.push({dist[used][v], v, used}); } if (used k !vis[used 1][v] d dist[used 1][v]) { dist[used 1][v] d; pq.push({dist[used 1][v], v, used 1}); } } } ll ans INF; for (int i 0; i k; i) { ans min(ans, dist[i][t]); } cout ans \n; return 0; }这份代码的复杂度是O((k1) * (nm) * log((k1)*n))空间是O((k1) * (nm))。对于 k10、n,m1e5 的题目运行时间大概在几百毫秒上下非常稳。我个人在实际做题里最常遇到的不是不会写而是写完之后怀疑自己“要不要把所有层都跑完”。其实 Dijkstra 一旦从堆里弹出终点 t 的某个状态能不能直接退出严格来说不能因为 Dijkstra 弹出的是最小距离状态但终点 t 可能在更高层有一个更小的距离还没有出堆。比如你当前弹出的是dist[0][t] 100但dist[3][t]可能还在堆里值是 80。普通 Dijkstra 里终点出堆就可以 return但分层图里必须等所有层的 t 状态都出堆才能确定最小值或者干脆跑完整张图再取 min。这个细节也容易让人掉坑。最后再分享一个小技巧如果免费次数 k 很大但实际有用的免费次数不会超过最短路径的边数可以尝试“按需更新”层数比如只有在当前层还有机会免费且走的边数没超过最短边数时才创建更高层的状态。但这种优化意义有限因为状态数量仍可能爆炸。真遇到 k 大的题果断换思路别在分层图上死磕。分层图最短路是一把很好用的“锤子”但也不是所有钉子都适合用锤子砸。理解它的适用边界和建图原理比背模板更重要。
