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

1. 从“一张图”到“多层世界”：分层图最短路的核心思想

如果你刷过一些算法题，尤其是涉及到“状态转移”或“有限次特殊操作”的最短路问题，很可能已经见过“分层图”这个概念。我第一次遇到它是在一道关于“在图中可以免费走K条边”的题目里，当时百思不得其解，直到看到题解里“建K+1层图”的提示，才恍然大悟。这感觉就像玩一个二维平面的游戏，突然给你开放了“楼层”的概念，整个解题空间瞬间从平面拓展到了立体。

简单来说，分层图最短路是一种建模技巧，它用于解决一类特殊的最短路问题：在标准的图结构（节点、边、权值）基础上，引入了“状态”或“次数限制”的维度。我们无法在原始的单一平面上同时表示不同的状态，于是最直观的方法就是——复制这个平面，建立多个“平行世界”（即层），每一层代表一种不同的状态（比如，已经使用了0次、1次、…、K次某种特殊权利）。层与层之间通过有向边连接，这些边就代表了“状态转移”（即使用一次特殊权利）。

举个例子，想象一个城市交通图（原始图），你有一张“特权卡”，可以让你免费通过任意一条道路（边），但只能用K次。在原始图上，你无法同时记录“已经用过几次特权”这个信息。分层图的做法是：建K+1层完全相同的图，第i层表示你已经使用了i次特权。那么：

• 在同一层内移动（走普通边），权值不变（支付原路费），状态（使用特权次数）也不变。
• 从第i层走到第i+1层（通过连接两层对应节点的“特权边”），权值为0（免费），但状态改变了（使用特权次数+1）。

这样，问题就转化为了在这个“立体”的分层图上，从起点（第0层）到终点（任意层）的最短路问题。Dijkstra或SPFA等标准最短路算法可以直接应用。

这个思想之所以强大，是因为它将一个带有“决策”的最优化问题，转化为了一个纯粹的、扩展后的图上的最短路问题。我们不再需要纠结于“何时使用特权”，算法会在所有可能的路径（包括所有可能的使用特权时机）中，自动找出总代价最小的那条。

2. 分层图的构建方法论：从抽象到具体

理解了核心思想，接下来就是如何动手构建。这绝不是简单复制粘贴图层那么简单，有几个关键细节决定了你代码的成败和效率。

2.1 确定“层”的含义与数量

这是建模的第一步，也是最关键的一步。你需要明确：每一层到底代表什么？

常见的“层”含义有：

1. 使用某种“特权”或“技能”的次数：如免费通过边K次、将某条边权值减半K次、逆向通过边K次等。层数通常是K+1（从0次到K次）。
2. 某种资源或属性的剩余量：比如油箱剩余油量（离散化后）、体力值、金钱数。这时层数可能由资源的上限决定。
3. 某种二元的“状态”：比如是否持有某个钥匙、是否访问过某个特殊节点。这时可能只需要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，向第i+1层的对应节点v_{i+1}连接一条权值为0的边（前提是原始图中u到v有边）。这表示在节点u处，使用一次特权，免费走到节点v，同时状态从i变为i+1。

一个极易出错的细节：层间边的方向。你必须想清楚，使用特权这个动作，是离开某个节点时发生的，还是到达某个节点时发生的？在绝大多数建模中，我们将其视为离开节点u时使用特权，因此边是从u_i指向v_{i+1}。这个方向性必须与题目描述的逻辑自洽。

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 邻接表存图与节点编号映射

由于分层图节点数激增，我们几乎总是使用邻接表（如vector<vector<pair<int, int>>>）来存图。这里的一个小技巧是节点编号的映射。

最清晰易懂的方法是定义一个函数，将(节点原始编号, 层数)映射到一个全局唯一的整数ID：

inline 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。

建模分析：

• “层”的含义：已经使用免费通行权的次数。共K+1层（0次， 1次， …， K次）。
• 层内边：对于原始图的每条无向边(u, v, w)，在每一层i，都添加两条有向边：u_i -> v_i权值w，v_i -> u_i权值w。这代表正常付费通行。
• 层间边：对于原始图的每条无向边(u, v, w)，对于每一层i(0 <= i < K)，添加两条有向边：u_i -> v_{i+1}权值0，v_i -> u_{i+1}权值0。这代表使用一次免费权通过这条边，同时使用次数+1。
• 起点与终点：起点为1_0。因为最多使用K次，所以终点可以是n_0, n_1, ..., n_K中的任意一个，答案取它们距离的最小值。

核心代码片段（C++）：

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; // (距离, 节点ID) const int INF = 0x3f3f3f3f; int n, m, K; vector<vector<pii>> g; // 分层图的邻接表 inline int get_id(int u, int k) { return k * n + u; } int dijkstra(int start, int end) { vector<int> dist(n * (K + 1), INF); dist[start] = 0; priority_queue<pii, vector<pii>, greater<pii>> 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_{i+1}的边权值不再是0，而是w / 2（向下取整）。这表示在u点使用一次“减半”特权，然后以半价通过这条边到达v。同样，也需要添加反向边v_i -> u_{i+1}，权值w / 2。
• 答案：同样取所有层终点距离的最小值。

与例题一的区别：层间边的权值从0变成了w/2。这完美体现了分层图的灵活性——层间边可以携带任何权值，只要它能正确表达“状态转移所付出的代价”。

3.3 例题三：寻找最短“升级”路径

问题描述：一个游戏地图是有向图，有些边是“普通道路”，有些边是“升级道路”。走“升级道路”需要消耗1点“升级点数”，但走完后，之后经过的所有边权值都会暂时减少一个固定值D（但不会低于0）。你初始有K点升级点数。求最短路。

建模分析： 这道题难度升级，因为状态转移的影响是持续性的，而不是一次性的。

• “层”的含义：这里的状态有两个维度吗？并不是。仔细思考，“之后所有边权值减少”这个效果，其实只取决于你是否处于“升级状态”。而“升级状态”是由你最后一次走升级道路后，还未走过任何普通道路来决定的。
• 一个巧妙的建模是：建立2*(K+1)层。
  • 第(2*i)层：表示当前未处于升级状态，并且已经使用了i次升级点数。
  • 第(2*i + 1)层：表示当前处于升级状态（即刚走过升级道路，增益效果还在），并且已经使用了i+1次升级点数（因为走升级边消耗了1点）。
• 边转移：
  1. 走普通边(u, v, w)：
     • 从未升级状态(2*i)层 -> 同层(2*i)的v，权值为w。
     • 从升级状态(2*i+1)层 -> 同层(2*i+1)的v，权值为max(0, w - D)（享受减益）。
  2. 走升级边(u, v, w)(消耗1点)：
     • 前提是i < K。
     • 从任何状态（层x）-> 进入升级状态(2*(i+1) + 1)层的v，权值为w（走升级边本身的权值，注意此时不享受减益，因为减益是走完之后才生效）。
• 起点与终点：起点在(2*0)层（未升级，用了0次）。终点可以是所有层的对应节点，取最小值。

这个例子说明，当状态更复杂时，我们可以通过增加层数（每层代表一个状态组合）来建模。关键在于明确定义每一层的状态，并设计好所有状态间的转移边。

4. 实战中的优化技巧与常见“坑点”

掌握了基本建模，在实际编码和解题中，还有一些技巧和陷阱需要留意。

4.1 空间与时间优化

分层图最大的开销在于节点和边的数量膨胀。假设原始图有N点M边，建L层。

• 节点数：N * L
• 边数：最坏情况下，每条原始边会衍生出L条层内边和(L-1)条层间边（双向则乘2），总计约O(M * L)。

优化策略：

1. 隐式建图：并不真的在内存中构造出完整的N*L个节点的邻接表。而是在Dijkstra算法松弛时，根据当前节点的ID，动态计算其邻居。例如，节点IDid，可以反推出原始节点u = id % N和层数lvl = id / N。当需要松弛时：
   • 走普通边：邻居ID是v + lvl * N，权值w。
   • 走特权边（如果lvl < K）：邻居ID是v + (lvl+1) * N，权值0（或w/2等）。 这样，我们只需要存储原始图，空间复杂度降为O(N + M)，但增加了计算开销。适用于N*L极大，无法显式建图的情况。
2. 状态压缩DP思想：对于某些特定问题（如“K次免费”），可以用DP思想。设dist[node][k]为到节点node使用了k次特权的最短距离。在Dijkstra的优先队列中存放三元组(d, node, k)。松弛时，分别向(node, k)走普通边和向(node, k+1)走特权边转移。这本质上是分层图思想，但省去了显式建层间边的过程，代码更紧凑。这是竞赛中最常见的写法。

   // 伪代码思路 vector<vector<int>> dist(n, vector<int>(K+1, INF)); dist[start][0] = 0; priority_queue<tuple<int, 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][k+1] > d + 0) { ... } // 免费 // 或者 if (k < K && dist[v][k+1] > d + w/2) { ... } // 减半 } }

4.2 易错点排查清单

1. 层间边的方向与权值：这是最高频的错误来源。务必根据题意画出一个简单的两层图（0层和1层），手动模拟一下“使用特权”这个过程，确认边是从哪层的哪个点指向哪层的哪个点，权值是多少。
2. 节点编号映射：如果使用一维ID映射，确保get_id和get_node/level函数互逆，且不会发生ID冲突。特别注意原始节点编号是0-index还是1-index，在输入和映射时要保持一致。
3. 终点状态：题目是要求“最多K次”还是“恰好K次”？这决定了答案是在所有dist[end][0...K]中取最小值，还是直接取dist[end][K]。
4. 特权使用次数与层数的关系：如果特权可以使用0到K次，那么总层数是K+1。数组大小和循环边界要格外小心，很容易写成K层，导致最后一次特权无法使用。
5. 图的无向/有向性：原始图是无向的，那么层内边和层间边都需要添加双向边。如果原始图是有向的，则必须严格按照方向添加。
6. 最短路算法选择：由于分层图边权均为非负（特权边权值可能是0，但也是非负），必须使用Dijkstra算法。使用SPFA在分层图上很容易因为边数过多而超时。
7. 初始化与无穷大：dist数组的初始化要足够大，且类型最好是long long，因为路径权值可能会累加得很大。使用0x3f3f3f3f作为int的INF，使用0x3f3f3f3f3f3f3f3f作为long long的INF是常见做法。

4.3 如何判断一个问题能用分层图解决？

当你遇到一个最短路问题时，可以问自己以下几个问题：

1. 问题是否在标准最短路的基础上，增加了“有限次数的特殊操作”？（如免费、减半、反向、升级等）
2. 这个“特殊操作”是否只与边有关，并且使用一次操作会改变后续的状态？
3. 这个状态的变化是否可以离散化地表示（如次数、剩余量、是否持有）？

如果答案都是“是”，那么分层图就很可能是一个正确的建模方向。它的本质是将“决策”（何时使用特权）转化为“状态”（已经用了多少次），并在扩展的图上用标准算法求解。

我个人经验是，分层图问题就像搭积木。核心是定义好“积木块”（每一层的状态），然后设计好“连接件”（层内边和层间边）。一旦模型建对，剩下的就是套用模板化的最短路算法。多练习几道题，你就能快速识别出这类问题的模式，并熟练地构建出对应的分层图模型。