分层图最短路：核心思想、建模方法与实战代码详解

1. 从“一张图”到“多层世界”分层图最短路的核心思想如果你刷过一些算法题尤其是涉及到“状态转移”或“有限次特殊操作”的最短路问题很可能已经见过“分层图”这个概念。我第一次遇到它是在一道关于“在图中可以免费走K条边”的题目里当时百思不得其解直到看到题解里“建K1层图”的提示才恍然大悟。这感觉就像玩一个二维平面的游戏突然给你开放了“楼层”的概念整个解题空间瞬间从平面拓展到了立体。简单来说分层图最短路是一种建模技巧它用于解决一类特殊的最短路问题在标准的图结构节点、边、权值基础上引入了“状态”或“次数限制”的维度。我们无法在原始的单一平面上同时表示不同的状态于是最直观的方法就是——复制这个平面建立多个“平行世界”即层每一层代表一种不同的状态比如已经使用了0次、1次、…、K次某种特殊权利。层与层之间通过有向边连接这些边就代表了“状态转移”即使用一次特殊权利。举个例子想象一个城市交通图原始图你有一张“特权卡”可以让你免费通过任意一条道路边但只能用K次。在原始图上你无法同时记录“已经用过几次特权”这个信息。分层图的做法是建K1层完全相同的图第i层表示你已经使用了i次特权。那么在同一层内移动走普通边权值不变支付原路费状态使用特权次数也不变。从第i层走到第i1层通过连接两层对应节点的“特权边”权值为0免费但状态改变了使用特权次数1。这样问题就转化为了在这个“立体”的分层图上从起点第0层到终点任意层的最短路问题。Dijkstra或SPFA等标准最短路算法可以直接应用。这个思想之所以强大是因为它将一个带有“决策”的最优化问题转化为了一个纯粹的、扩展后的图上的最短路问题。我们不再需要纠结于“何时使用特权”算法会在所有可能的路径包括所有可能的使用特权时机中自动找出总代价最小的那条。2. 分层图的构建方法论从抽象到具体理解了核心思想接下来就是如何动手构建。这绝不是简单复制粘贴图层那么简单有几个关键细节决定了你代码的成败和效率。2.1 确定“层”的含义与数量这是建模的第一步也是最关键的一步。你需要明确每一层到底代表什么常见的“层”含义有使用某种“特权”或“技能”的次数如免费通过边K次、将某条边权值减半K次、逆向通过边K次等。层数通常是K1从0次到K次。某种资源或属性的剩余量比如油箱剩余油量离散化后、体力值、金钱数。这时层数可能由资源的上限决定。某种二元的“状态”比如是否持有某个钥匙、是否访问过某个特殊节点。这时可能只需要2层持有/未持有。数量计算假设原始图有N个节点需要建立L层。那么分层图的总节点数就是N * L。这是一个非常重要的数量级直接影响到你算法的复杂度和内存开销。在解题时务必先估算这个乘积确保在题目限制通常是N * L 1e5或1e6量级之内。2.2 设计层内边与层间边这是构建分层图的实体步骤。层内边直接复制原始图的边。对于第i层的节点u_i如果原始图中u到v有一条权值为w的边那么在分层图中就从u_i向v_i连接一条权值为w的边。这表示不改变状态的移动。层间边这是分层图的灵魂。它代表了状态转移。通常是从低状态层指向高状态层或状态发生变化的层。例如对于“免费通过”特权从第i层的节点u_i向第i1层的对应节点v_{i1}连接一条权值为0的边前提是原始图中u到v有边。这表示在节点u处使用一次特权免费走到节点v同时状态从i变为i1。一个极易出错的细节层间边的方向。你必须想清楚使用特权这个动作是离开某个节点时发生的还是到达某个节点时发生的在绝大多数建模中我们将其视为离开节点u时使用特权因此边是从u_i指向v_{i1}。这个方向性必须与题目描述的逻辑自洽。2.3 超级源点与超级汇点起点和终点也需要在分层图中定位。起点通常固定在第0层的起点节点s_0。因为初始状态是未使用任何特权。终点视题目要求而定。如果题目要求“最多使用K次特权”那么终点可以是任意层的终点节点t_i(0 i K)。最终答案就是min(dist[t_0], dist[t_1], ..., dist[t_K])其中dist是从s_0出发的最短距离。如果题目要求“必须使用完K次特权”或“恰好使用K次”那么终点就是第K层的终点节点t_K。为了简化代码我们可以在建完分层图后从s_0跑一次单源最短路如Dijkstra然后遍历所有层的终点节点取最小值或者直接读取dist[t_K]。2.4 邻接表存图与节点编号映射由于分层图节点数激增我们几乎总是使用邻接表如vectorvectorpairint, int来存图。这里的一个小技巧是节点编号的映射。最清晰易懂的方法是定义一个函数将(节点原始编号, 层数)映射到一个全局唯一的整数IDinline int get_id(int node, int level) { return level * n node; // 假设原始节点编号从0到n-1 }这样get_id(u, i)就代表了第i层的节点u。在添加边时无论是层内边还是层间边都使用这个映射后的ID来操作逻辑会非常清晰。踩坑实录早期我尝试用三维数组dist[level][node]来记录距离虽然直观但在使用优先队列做Dijkstra时需要把(level, node)打包成结构体并重载比较运算符代码稍显繁琐。而使用一维ID映射后dist[]数组是一维的优先队列直接存储(distance, id)代码更简洁也不易出错。3. 经典例题拆解从建模到代码实现理论说再多不如看实战。我们通过几道经典例题来彻底掌握分层图的用法。我会重点讲清建模思路而不仅仅是贴代码。3.1 例题一K次免费通行权问题描述给定一个n个点m条边的无向图每条边有一个正权值路费。你拥有K次机会可以免费通过任意一条边。求从点1到点n的最小总花费。1 K 10,n, m 1e4。建模分析“层”的含义已经使用免费通行权的次数。共K1层0次 1次 … K次。层内边对于原始图的每条无向边(u, v, w)在每一层i都添加两条有向边u_i - v_i权值wv_i - u_i权值w。这代表正常付费通行。层间边对于原始图的每条无向边(u, v, w)对于每一层i(0 i K)添加两条有向边u_i - v_{i1}权值0v_i - u_{i1}权值0。这代表使用一次免费权通过这条边同时使用次数1。起点与终点起点为1_0。因为最多使用K次所以终点可以是n_0, n_1, ..., n_K中的任意一个答案取它们距离的最小值。核心代码片段C#include bits/stdc.h using namespace std; typedef pairint, int pii; // (距离, 节点ID) const int INF 0x3f3f3f3f; int n, m, K; vectorvectorpii g; // 分层图的邻接表 inline int get_id(int u, int k) { return k * n u; } int dijkstra(int start, int end) { vectorint dist(n * (K 1), INF); dist[start] 0; priority_queuepii, vectorpii, greaterpii pq; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 旧的最优值跳过 for (auto [v, w] : g[u]) { if (dist[v] d w) { dist[v] d w; pq.emplace(dist[v], v); } } } int ans INF; // 遍历所有层的终点取最小值 for (int k 0; k K; k) { ans min(ans, dist[get_id(end, k)]); } return ans; } int main() { cin n m K; int start 1, end n; // 假设起点终点编号为1和n g.resize(n * (K 1)); for (int i 0; i m; i) { int u, v, w; cin u v w; // 注意输入节点编号如果从1开始我们的get_id函数内部用n做乘法这里u,v需要先减1如果内部编号从0开始 // 为清晰起见假设我们已将节点转为0-index: u--; v--; for (int k 0; k K; k) { // 添加层内边双向付费 int u_id get_id(u, k); int v_id get_id(v, k); g[u_id].emplace_back(v_id, w); g[v_id].emplace_back(u_id, w); // 添加层间边双向免费 if (k K) { int u_id_next get_id(u, k 1); int v_id_next get_id(v, k 1); // 从当前层u到下一层v使用一次免费 g[u_id].emplace_back(v_id_next, 0); // 从当前层v到下一层u使用一次免费 g[v_id].emplace_back(u_id_next, 0); } } } int start_id get_id(start, 0); // 起点在第0层 int ans dijkstra(start_id, end); cout (ans INF ? -1 : ans) endl; return 0; }注意事项上述代码为了清晰展示了所有边的添加过程。实际上层内边和层间边的添加可以合并到一个循环中但分开写更利于理解和调试。另外节点编号从0还是1开始需要统一小心处理差一错误。3.2 例题二边权减半K次问题描述与上题类似但特权不是免费而是可以将任意一条边的权值减半向下取整最多使用K次。求最短路。建模分析 这道题是分层图的经典变种它揭示了层间边权值不一定为0。“层”的含义同上使用“减半”特权的次数。层内边同上权值w。层间边对于边(u, v, w)从u_i到v_{i1}的边权值不再是0而是w / 2向下取整。这表示在u点使用一次“减半”特权然后以半价通过这条边到达v。同样也需要添加反向边v_i - u_{i1}权值w / 2。答案同样取所有层终点距离的最小值。与例题一的区别层间边的权值从0变成了w/2。这完美体现了分层图的灵活性——层间边可以携带任何权值只要它能正确表达“状态转移所付出的代价”。3.3 例题三寻找最短“升级”路径问题描述一个游戏地图是有向图有些边是“普通道路”有些边是“升级道路”。走“升级道路”需要消耗1点“升级点数”但走完后之后经过的所有边权值都会暂时减少一个固定值D但不会低于0。你初始有K点升级点数。求最短路。建模分析 这道题难度升级因为状态转移的影响是持续性的而不是一次性的。“层”的含义这里的状态有两个维度吗并不是。仔细思考“之后所有边权值减少”这个效果其实只取决于你是否处于“升级状态”。而“升级状态”是由你最后一次走升级道路后还未走过任何普通道路来决定的。一个巧妙的建模是建立2*(K1)层。第(2*i)层表示当前未处于升级状态并且已经使用了i次升级点数。第(2*i 1)层表示当前处于升级状态即刚走过升级道路增益效果还在并且已经使用了i1次升级点数因为走升级边消耗了1点。边转移走普通边(u, v, w)从未升级状态(2*i)层 - 同层(2*i)的v权值为w。从升级状态(2*i1)层 - 同层(2*i1)的v权值为max(0, w - D)享受减益。走升级边(u, v, w)(消耗1点)前提是i K。从任何状态层x- 进入升级状态(2*(i1) 1)层的v权值为w走升级边本身的权值注意此时不享受减益因为减益是走完之后才生效。起点与终点起点在(2*0)层未升级用了0次。终点可以是所有层的对应节点取最小值。这个例子说明当状态更复杂时我们可以通过增加层数每层代表一个状态组合来建模。关键在于明确定义每一层的状态并设计好所有状态间的转移边。4. 实战中的优化技巧与常见“坑点”掌握了基本建模在实际编码和解题中还有一些技巧和陷阱需要留意。4.1 空间与时间优化分层图最大的开销在于节点和边的数量膨胀。假设原始图有N点M边建L层。节点数N * L边数最坏情况下每条原始边会衍生出L条层内边和(L-1)条层间边双向则乘2总计约O(M * L)。优化策略隐式建图并不真的在内存中构造出完整的N*L个节点的邻接表。而是在Dijkstra算法松弛时根据当前节点的ID动态计算其邻居。例如节点IDid可以反推出原始节点u id % N和层数lvl id / N。当需要松弛时走普通边邻居ID是v lvl * N权值w。走特权边如果lvl K邻居ID是v (lvl1) * N权值0或w/2等。 这样我们只需要存储原始图空间复杂度降为O(N M)但增加了计算开销。适用于N*L极大无法显式建图的情况。状态压缩DP思想对于某些特定问题如“K次免费”可以用DP思想。设dist[node][k]为到节点node使用了k次特权的最短距离。在Dijkstra的优先队列中存放三元组(d, node, k)。松弛时分别向(node, k)走普通边和向(node, k1)走特权边转移。这本质上是分层图思想但省去了显式建层间边的过程代码更紧凑。这是竞赛中最常见的写法。// 伪代码思路 vectorvectorint dist(n, vectorint(K1, INF)); dist[start][0] 0; priority_queuetupleint, int, int pq; // (-距离, 节点, 已用次数) pq.emplace(0, start, 0); while (!pq.empty()) { auto [d, u, k] pq.top(); pq.pop(); d -d; if (d dist[u][k]) continue; for (auto [v, w] : original_graph[u]) { // 情况1: 不用特权 if (dist[v][k] d w) { ... } // 情况2: 用特权 (如果k K) if (k K dist[v][k1] d 0) { ... } // 免费 // 或者 if (k K dist[v][k1] d w/2) { ... } // 减半 } }4.2 易错点排查清单层间边的方向与权值这是最高频的错误来源。务必根据题意画出一个简单的两层图0层和1层手动模拟一下“使用特权”这个过程确认边是从哪层的哪个点指向哪层的哪个点权值是多少。节点编号映射如果使用一维ID映射确保get_id和get_node/level函数互逆且不会发生ID冲突。特别注意原始节点编号是0-index还是1-index在输入和映射时要保持一致。终点状态题目是要求“最多K次”还是“恰好K次”这决定了答案是在所有dist[end][0...K]中取最小值还是直接取dist[end][K]。特权使用次数与层数的关系如果特权可以使用0到K次那么总层数是K1。数组大小和循环边界要格外小心很容易写成K层导致最后一次特权无法使用。图的无向/有向性原始图是无向的那么层内边和层间边都需要添加双向边。如果原始图是有向的则必须严格按照方向添加。最短路算法选择由于分层图边权均为非负特权边权值可能是0但也是非负必须使用Dijkstra算法。使用SPFA在分层图上很容易因为边数过多而超时。初始化与无穷大dist数组的初始化要足够大且类型最好是long long因为路径权值可能会累加得很大。使用0x3f3f3f3f作为int的INF使用0x3f3f3f3f3f3f3f3f作为long long的INF是常见做法。4.3 如何判断一个问题能用分层图解决当你遇到一个最短路问题时可以问自己以下几个问题问题是否在标准最短路的基础上增加了“有限次数的特殊操作”如免费、减半、反向、升级等这个“特殊操作”是否只与边有关并且使用一次操作会改变后续的状态这个状态的变化是否可以离散化地表示如次数、剩余量、是否持有如果答案都是“是”那么分层图就很可能是一个正确的建模方向。它的本质是将“决策”何时使用特权转化为“状态”已经用了多少次并在扩展的图上用标准算法求解。我个人经验是分层图问题就像搭积木。核心是定义好“积木块”每一层的状态然后设计好“连接件”层内边和层间边。一旦模型建对剩下的就是套用模板化的最短路算法。多练习几道题你就能快速识别出这类问题的模式并熟练地构建出对应的分层图模型。