图论算法我写过不少但真要论思路巧妙、代码好写、还能在实战里反复用上的分层图最短路绝对排得上号。这个技巧解决的是非常具体的一类问题给你一张图允许你从中选最多 k 条边把它们的权值变成 0问从起点到终点的最短路径是多少。换句话说就是“免费 k 条边”。很多初学者第一眼看到这题会懵心想这不就是贪心选最大的 k 条边去掉吗还真不是。因为路径是连续的你免掉哪几条边取决于整条路径怎么走前面选了免费的边后面路径的选择空间就会变大这是典型的全局最优问题不能靠局部贪心。我当年第一次做这类题也试着排序去掉大边结果 WA 到怀疑人生。这篇博客我打算把分层图最短路从原理、建图、代码到坑点一次讲透。不管你是打 ACM、刷力扣还是做算法面试准备只要把分层图的“拆层”思想吃透这类“限制次数”的图论题基本就都拿下了。1. 先搞清楚问题免费 k 条边到底在算什么1.1 一个场景代入先看一个最经典的场景。假设你需要规划一条从 A 城市到 B 城市的行程中间经过若干城市每条道路都有通行费。你手里有 k 张“免费通行券”每张券可以免掉一条路的费用。注意每张券只能用一次而且不需要在同一段路上你想在哪几条路上用都行。问题最少花多少钱能到 B 城这听起来有点像“砍掉最大的 k 个费用”但为什么不行我给你举个例子。假设路径有两条可选路径 1费用是 100、1、1总费用 102路径 2费用是 50、50、50总费用 150如果 k1从“去掉最大边”的角度看路径 1 去掉 100 后费用是 2路径 2 去掉一个 50 后费用是 100显然路径 1 好。但问题来了——如果你一开始为了走某条中间路段必须先经过那段 100 的费用那你必须把券用在那后面可能还有别的收费边需要免券不够了。所以选路径不只是看哪条“最大边大”而是看整条链上费用的分布。更极端一点的例子有一条路中间有一段费用是 1000但它连接了一个“后门”通过后门之后所有路都免费。如果你不把券用在 1000 这段你根本到不了后门。贪心按边排序的时候根本不会想到这一点。所以这类问题的本质是边的选择会影响后续路径的决策这是一个有后效性的问题不能简单拆分。1.2 为什么直接跑最短路不行如果题目没有“免费 k 条边”这个条件那就是标准的最短路Dijkstra 一把梭就完事了。但现在有了“可以免掉 k 条边的权值”这个选项问题就变了最短路的“状态”不单单是“我在哪个点”还得包含“我已经用了多少次免费名额”。你想想就算两个人站在同一个点一个人还剩 3 次免费机会另一个一次都没用过他们接下来的最优路径是可能完全不同的。前者可以肆无忌惮地走收费高的边后者只能精打细算。所以传统 Dijkstra 里 dist[u] 只记录“到 u 点最短距离”是不够的这个信息丢失了“剩余免费次数”这一关键维度。如果你非要用普通最短路硬做那就只能暴力枚举哪 k 条边免费。可 k 一大组合数爆炸根本不现实。分层图最短路的核心想法就是把“用了多少次免费机会”也变成图的一部分让每一个状态都有对应的“节点”这样就能继续用最短路算法求解了。2. 分层图的核心原理用复制图来记录“状态”2.1 从 DP 的角度理解分层图最短路本质上就是把动态规划的思想揉进最短路里。我们定义一个状态 dist[i][j] 表示“到达点 i已经使用了 j 次免费机会”时的最小花费。从这里出发有两种转移方式走一条边但不使用免费机会dist[v][j] min(dist[v][j], dist[u][j] w)走一条边使用一次免费机会dist[v][j1] min(dist[v][j1], dist[u][j])注意第二个转移里边权 w 被直接丢掉了这就是“免费”的含义。你不需要为这条边付任何费用但要消耗一次免费机会。一旦把状态定义成这样你发现这已经是一个二维 DP 了。但为什么还要叫“分层图”呢因为图论里天然的思维是把状态当作节点把转移当作边。dist[i][j] 是一个状态我们可以把它看作“第 j 层图里的点 i”。2.2 图怎么分层画出来其实不难很多人一听“分层图”就觉得很高大上其实画出来特别直白。想象你有 k1 张完全一样的原图编号为第 0 层、第 1 层、……、第 k 层。第 0 层表示“一次免费都没用”第 1 层表示“已经用了 1 次免费”以此类推。每张层内部原图里的边保持不变照常连接。比如原图里有 u 到 v 权重 w 的边那么在每一层内部都有 u 到 v 权重 w 的边表示“这层状态下正常付费走这条边”。然后关键来了在第 i 层和第 i1 层之间我们要连“免费边”。具体来说如果原图有 u 到 v 权重 w 的边那么在第 i 层的 u 到第 i1 层的 v 之间连一条权重为 0 的边表示“从这一层出发用掉一次免费机会跳过 w 的费用直接到下一层”。![分层图结构示意这里用文字描述第0层到第k层的纵向连接]用文字描述就是这样你有一栋 k1 层的楼每层楼都有一张相同的道路网。你在一楼走路要交钱但你找到一部电梯每坐一次电梯可以免掉当前这条路的路费但会把你送到上一层楼。到了上一层你继续走道路网仍然要交钱但还能再坐电梯。最多坐 k 次电梯问从一楼起点到任意楼层终点的最少花费。这个“电梯”就是层间的零权边。目标点虽然可能在任意一层但因为我们最多只用 k 次免费所以答案要取 dist[t][0]、dist[t][1]、……、dist[t][k] 里面的最小值。2.3 建图和复杂度分层之后的图是什么规模这个一定要算清楚不然代码写完直接内存超限。假设原图有 n 个点、m 条边。分层之后节点数量(k1) × n边数量每层内部有 m 条边共 (k1) × m 条层间每层有 m 条“免费边”共 k × m 条。所以总边数大约是 (2k1) × m这意味着如果 k 特别大比如 k100000而 n10000、m100000那总节点数会是 10 亿级别内存直接爆炸。所以分层图最短路并不是什么时候都能用它对 k 的大小有要求。一般来说当 (k1) × n 在百万级别以内时分层图是最优选。时间复杂度上Dijkstra 堆优化的复杂度是 O(E log V)这里的 V 和 E 都是扩层之后的规模所以整体是 O((2k1)·m · log((k1)·n))。如果 k 很小比如 k≤10这就是一个非常快的算法。3. 代码实现两种写法都能过3.1 写法一显式建出 k1 层图理解了分层图原理之后第一种实现方式非常直观真正在代码里建出 (k1)×n 个节点然后按规则连边跑一遍普通 Dijkstra。节点编号怎么设计一个常见方案是把第 i 层的第 u 个点映射为 i * n u假设点编号从 0 开始。这样第 0 层是 0 到 n-1第 1 层是 n 到 2n-1依次类推。#include bits/stdc.h using namespace std; const int MAXNODE 1000005; // 根据实际规模调整 struct Edge { int to, w, next; } edge[MAXNODE * 2]; int head[MAXNODE], tot; void add_edge(int u, int v, int w) { edge[tot] {v, w, head[u]}; head[u] tot; } int n, m, k, s, t; int dist[MAXNODE]; bool vis[MAXNODE]; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { int u pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i; i edge[i].next) { int v edge[i].to, w edge[i].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], 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, w; scanf(%d%d%d, u, v, w); for (int layer 0; layer k; layer) { int u_id layer * n u; int v_id layer * n v; add_edge(u_id, v_id, w); add_edge(v_id, u_id, w); // 无向图 // 层间免费边 if (layer k) { add_edge(u_id, layer * n n v, 0); add_edge(v_id, layer * n n u, 0); } } } dijkstra(); int ans INT_MAX; for (int layer 0; layer k; layer) { ans min(ans, dist[layer * n t]); } printf(%d\n, ans); return 0; }注意几个细节。第一这里我默认是无向图所以要加双向边如果题目是有向图那就只加单向边。第二最终答案要在所有层里取最小值因为免费次数不一定用完。第三编号时如果用 1 到 n 的节点编号就需要用 layer * n u 这种映射时要小心我建议统一把点编号改成 0 到 n-1或者用 layer * (n 1) u 来避免混淆。这个写法思路清晰但开销也大每条原边都要复制 k1 份如果 k 稍微大一点建图过程就会比较占用内存和时间。3.2 写法二二维 dist 状态转移推荐其实我不太推荐显式建图因为代码里会出现大量重复的 add_edge 调用而且一不小心就把“层数 × 点数”的编号搞混。我更习惯的写法是用二维 dist 数组 优先队列直接做状态转移代码更短也更不容易出错。核心思想是只存一份原图Dijkstra 的时候每个状态由一个三元组组成(当前最小花费, 当前点, 已经用掉的免费次数)。每次从堆里弹出状态后尝试两种转移正常付费走边或者用免费次数走边。#include bits/stdc.h using namespace std; const int MAXN 10005; const int MAXK 15; // k 的一般范围 struct Edge { int to, w, next; } edge[MAXN * 2]; int head[MAXN], tot; void add_edge(int u, int v, int w) { edge[tot] {v, w, head[u]}; head[u] tot; } int n, m, k, s, t; int dist[MAXN][MAXK]; bool vis[MAXN][MAXK]; struct Node { int d, u, layer; bool operator(const Node other) const { return d other.d; } }; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); priority_queueNode, vectorNode, greaterNode pq; dist[s][0] 0; pq.push({0, s, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u, layer cur.layer, d cur.d; if (vis[u][layer]) continue; vis[u][layer] true; for (int i head[u]; i; i edge[i].next) { int v edge[i].to, w edge[i].w; // 不使用免费机会 if (dist[v][layer] d w) { dist[v][layer] d w; pq.push({dist[v][layer], v, layer}); } // 使用一次免费机会跳到下一层 if (layer k dist[v][layer 1] d) { dist[v][layer 1] d; pq.push({dist[v][layer 1], v, layer 1}); } } } } int main() { scanf(%d%d%d, n, m, k); scanf(%d%d, s, t); for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); add_edge(u, v, w); add_edge(v, u, w); } dijkstra(); int ans INT_MAX; for (int layer 0; layer k; layer) { ans min(ans, dist[t][layer]); } printf(%d\n, ans); return 0; }这个写法的好处有几点。一是原图只存一份内存友好不需要真的复制 k1 层。二是状态转移的逻辑就是 DP 式的写出来直白不容易把层编号搞混。三是如果你做的是其他“限制次数”的变体比如“最多半价 k 次”只需要改一下第二个转移的权值就行非常灵活。我在实际刷题时只要 k 的范围在二维数组能承受的范围内比如 k≤1000n≤10000那 dist 数组就是 10^7 级别还能接受我基本都写第二种。3.3 空间计算与优化关于空间这里有个特别容易踩的坑。很多题里 k 的取值范围很迷比如 n10000k1000000这要是用二维数组那是 10^10 个数直接 MLE 到怀疑人生。这时候必须换个思路。第一种优化是滚动数组。因为在层之间的转移是单向的只能从第 i 层到第 i1 层我们其实可以只保存两层的 dist 数组一层一层地跑。但问题是同一层内部的 Dijkstra 也会更新同层状态直接滚动会有麻烦。不过在竞赛里这种 k 特别大的情况通常是另一种解法——用 DP 最短路的思想把“免费 k 次”变成“分层图 二分答案”之类的操作题面一般会留出其他突破口。第二种优化是直接压缩到一维数组。如果 k 很大但图的边权都非负那么“免费 k 条边”其实等价于在原图上跑一个带“费用”约束的最短路可以用“最短路径 免费券”的变形算法。但通常没必要考试和面试里出现的分层图题k 基本都在可控范围内。我的建议是开数组之前先心算一遍dist[n][k1] 占多少内存如果是 int一个元素 4 字节10^7 个元素就是 40MB配合其他数组可能逼近内存上限这时候可以用 short、long long 混搭或者把 dist 换成 vector 动态开。4. 我踩过的坑和排查技巧4.1 常见问题速查表我把分层图这类题最容易犯的错整理成了一张表每一条都是我自己或身边朋友真实踩过的花几分钟看一下能省很多调试时间。问题原因解决方案答案永远比预期大结果没在 k1 层里取最小值最后循环 layer0..k取 min(dist[t][layer])内存超限MLEk×n 超出数组容量改用二维 dist 状态转移写法或压缩层数超时TLE堆里塞了太多无效状态加 vis 数组队首弹出已访问状态直接跳过建图后路径错乱层节点编号算错显式建图时统一编号规则推荐 layer*(n1)u免费边只加了一个方向无向图漏了反向层间边每条无向边两个方向的层间边都要加起点在第 0 层终点在随机层终点可能是任意层答案必须取所有层的最小值边权太大导致 int 溢出累加距离超过 int 范围使用 long long 存 dist4.2 几个隐蔽的坑除了表格里的常规问题还有三个隐蔽的坑我每次写都要格外小心。第一个是“免费次数不一定用完”。这说起来简单但很多初学者会在最后输出 dist[t][k]觉得就是用了最多的免费名额。可万一最优路径根本不需要用满 k 次呢比如 k5但最短路径上本来就只有 3 条需要付费的边那答案应该是 dist[t][3]而不是 dist[t][5]。我在代码里最后取 min 就是专门防这个。第二个是“层间免费边本质是状态转移不是真的边”。如果你显式建图可能会顺手在原图的每个边上都加一条零权边结果一路零权“白嫖”到底这思路就错了。分层图的精髓在于每用一次免费机会就必须“升一层”而每一层内部还是有正常权值的。如果你不限制层数零权边连成一片那 Dijkstra 直接沿着零权边跑答案永远都是 0。第三个是“起点在第 0 层还是任意层”。如果题目允许你在起点就用掉免费机会虽然这没啥意义因为起点没有入边你从第 0 层起点开始跑是没问题的。但如果你写的转移是从第 i 层起点跳到第 i1 层那可能导致 dist 更新链路出问题。最稳妥的做法是只从第 0 层起点开始层间转移只在走边时发生。4.3 什么时候分层图会失效分层图不是万能的它有两个天然的限制。第一个限制是“免费次数必须比路径长度小很多”。如果 k 非常大比如 k≥n那么分层图的状态数会爆炸内存和时间都撑不住。这时的题目往往会有更巧妙的解法比如观察到免费边足够多时答案就是 0如果起点和终点连通或者退化成最短路本身。第二个限制是“图里不能有负权环”。如果图里有负权边Dijkstra 直接用不了分层图也只是把这个负权图复制了 k1 份解决不了负环问题。碰到负权的情况你可能得用 SPFA 加上分层图的思路但效率就会低很多。竞赛题里分层图最短路默认都是非负权图这点要注意。第三个限制是“状态维度的边界”。分层图的思想适合“只有一维附加状态”的问题如果你同时要限制“免费 k 条边”和“最多走 m 条边”那就需要三维状态图的规模会进一步膨胀往往就不划算了。5. 不只是免费边分层图的扩展玩法5.1 打折、半价、限免的组合分层图的思想最牛的地方在于它不只能处理“免费 k 条边”任何“带有次数限制的特殊操作”都可以用这个模型来套。举几个例子打折 k 次每次可以用一张折扣券边权变成原来的 50%。那么层间转移的边权就是 w/2而不是 0。反向走 k 次有些边只能正向走但允许你最多逆向经过 k 条边。那么层间转移就是“从 v 到 u”方向建一条零权边。加速 k 次每次加速可以让边权清零但加速后的路段不能再用第二次加速。这本质上还是“免费 k 条边”只是题目包装不同。核心思路完全一样把“操作次数”作为分层的一维每使用一次操作状态就移动到下一层。5.2 分层图与状态压缩、DP 的联动分层图再往下走就是更广义的“状态图”思想。你可以把任何影响后续决策的状态编码成图上的节点。比如需要访问某些关键点的“旅行商问题”是状态压缩 最短路带有油耗限制的路径规划是“剩余油量层”的最短路某种“道具”只能在特定节点使用的也可以分层这个思路的关键是问你一个问题一条路径走到某个点有哪些信息会影响接下来的选择把这些信息拆成离散的维度每个维度加进状态里图论算法就能帮你算出带约束的最优路径。我印象很深的一道扩展题是给定一张图每条边有时间和费用两个属性要求在费用不超过限定值的情况下求最短时间。这其实也是一个二维状态最短路dist[费用][点] 最短时间本质上就是分层图的变体只是“层”变成了“已消耗的费用”。5.3 推荐练习与总结思路如果你想练熟分层图我建议按这个顺序刷题先做一道基础的“免费 k 条边”裸题把两种代码都写一遍确保理解层间转移再做一道带方向的变体比如“可以逆向走 k 条边”体会层间边方向的不同然后做一道把分层和二分答案结合的题比如“最小化最大边权”这类题往往要用分层图判断可行性最后尝试自己写一道“打折 k 次”的题把层间边权改成 w/2看看会不会在数据溢出上翻车做完这一圈你对“状态图”这个概念基本就建立起来了。以后再看到任何“限制操作次数”的图论题第一反应就是能不能分层而不是傻傻地枚举组合。我个人在实际做题中的体会是分层图最短路最难的其实不是算法本身而是你能不能想到“操作次数”也可以变成状态。一旦想到这一层代码反而是整个流程里最简单的一环——它就是 Dijkstra 加了一个维度而已。所以如果你在考场上碰到这类题卡住了别急着想数学推导先把“状态有哪些维度”写下来画一画状态转移图答案往往自己就出来了。