分层图最短路：用“平行宇宙”思想解决有限制的最优路径问题

1. 项目概述：当最短路问题遇上“平行宇宙”

搞图论和算法优化的朋友，对最短路算法肯定不陌生，Dijkstra、Bellman-Ford、SPFA这些名字闭着眼睛都能背出来。常规的最短路问题，我们处理的是一张静态的图，边权固定，目标明确：找到从起点到终点的最短路径。但实际项目中，我们总会遇到一些“不讲武德”的场景：比如，你开车导航，有免费的高速公路可以走，但限次数；或者，你玩一个游戏，地图上有一些特殊道具，使用后能让你瞬间穿越到另一层地图，但道具数量有限。这些问题，本质上都是在问你：在拥有有限次“改变状态”或“打破规则”能力的前提下，如何规划出最优路径？

这就是分层图最短路（Layered Graph Shortest Path）要解决的经典问题。我第一次在比赛中遇到它时，感觉像是打开了新世界的大门——原来最短路还能这么玩！它不再将问题局限在单一的二维平面上，而是通过“复制”原图，构建出多个平行的图层，每个图层代表一种不同的状态或资源使用情况。层与层之间通过特定的“层间边”连接，这些边就对应着那些“打破规则”的操作，比如使用一次免费机会、穿越一次时空门。

理解分层图，关键在于理解这种“状态扩展”的思想。它把动态决策过程（何时使用特殊能力）巧妙地转化为了在一个静态的、但规模更大的图上的静态最短路问题。这样一来，我们就可以祭出那些成熟、高效的最短路算法来一招制敌。掌握这个方法，不仅能让你在算法竞赛中多一件趁手的兵器，更能让你在面对某些复杂的现实优化问题时，拥有一个清晰而强大的建模工具。接下来，我就结合几个经典的例题，带你彻底吃透分层图的构建、实现以及那些藏在细节里的“魔鬼”。

2. 核心思想与建模拆解：如何构建你的“平行世界”

分层图的核心，在于对“状态”的建模。我们不再仅仅关心“我在哪个点”，更要关心“我还剩多少特殊能力可以使用”或者“我当前处于哪种模式”。这个附加的维度，就是“层”。

2.1 分层图的基本构造原理

想象原图有N个节点。现在我们有一种特殊操作（比如“走一次免费边”），最多可以使用K次。那么，最直观的分层图构建方式就是：

1. 复制图层：我们创建(K+1)个完全相同的原图副本。第0层代表一次特殊操作都还没用过的状态，第1层代表用过1次的状态，以此类推，直到第K层代表已经用完了全部K次机会的状态。
2. 层内边：每个图层内部，边的连接关系和权值与原图完全一致。这代表了在不使用特殊能力时，正常的移动方式。
3. 层间边：这是分层图的灵魂。它连接了不同图层上的同一个原始节点。例如，从第i层的节点u（即状态(u, i)），可以有一条有向边指向第i+1层的节点v（即状态(v, i+1)）。这条边的权值，就代表了“在节点u处使用一次特殊能力，到达节点v”的代价。这个代价可能是0（免费），可能是某个固定值，也可能是某种计算后的值。

这样，整个问题就转化为：在这个拥有N * (K+1)个节点的分层图上，求从起点(start, 0)（起点，未使用能力）到任意终点(end, i)（i从 0 到 K）的最短距离。最终答案就是min(dist[(end, i)])，因为我们不强制用完所有能力，只要到达终点就行。

注意：层间边的方向至关重要。它必须是单向的，从低使用次数的层指向高使用次数的层。这确保了特殊能力的使用次数是单调递增的，不可能出现“回溯”使用次数的情况，避免了状态转移出现环，也符合我们“有限次数”的设定。

2.2 两种经典建模场景深度剖析

分层图的建模并非一成不变，根据“特殊操作”作用的对象不同，主要有两种经典模式。

2.2.1 模式一：对“边”进行操作（如：使某条边免费/半价）

这是最经典的场景，对应“有 K 次机会，可以忽略某条边的权值（或将其改为另一个值）”这类问题。

• 建模方法：

  • 层内边：权值w，代表原边代价。
  • 层间边：从(u, i)到(v, i+1)，权值为0（或w'，如果半价）。这表示在u点，我们决定对接下来走到v的这条边使用一次特殊能力，使其代价减免。

• 为什么这样建？关键在于，特殊能力的作用对象是“从 u 到 v 的移动行为本身”。因此，层间边需要连接的是下一个将要到达的节点 v。决策点在于站在u时，决定是否对即将踏上的这条边使用能力。

2.2.2 模式二：对“点”进行操作（如：在某个点进行状态切换）

另一种常见场景是“有 K 次机会，在某个点可以进行瞬间移动/状态切换”。例如，在某个城市可以坐飞机直达另一个城市，但机票有限。

• 建模方法：

  • 层内边：权值w，代表原边代价（如驾车）。
  • 层间边：从(u, i)到(v, i+1)，权值为0或一个固定值（机票价）。注意，这里的u和v可以是任意两个点，代表了从u点直接飞往v点。

• 与模式一的区别：此时，特殊能力的作用对象是“在点 u 处进行传送”。层间边连接的v可以是图中任意其他节点，而不仅仅是原图中与u直接相连的节点。这通常意味着层间边的数量会远多于模式一。

2.2.3 一个必须想清楚的思维陷阱

很多新手在建模时容易混淆：层间边应该连接当前层的u到下一层的u，还是当前层的u到下一层的v？

答案是：连接(u, i)到(v, i+1)。

• 连接(u, i)到(u, i+1)意味着什么？意味着“在u点使用了一次能力，但还停留在u点”。这通常没有意义，除非能力的效果是“在本地进行状态切换”（比如充电、切换装备）。对于绝大多数“移动类”能力，使用能力一定伴随着位置的改变。
• 因此，务必根据题意明确：使用特殊能力这个动作，是附着在一次移动（边）上，还是附着在一个停留点（点）上？这直接决定了层间边的连接方式。

2.3 空间与时间复杂度分析

分层图通过增加维度（层）来转化问题，代价就是图规模的扩大。

• 节点数：N * (K+1)。
• 边数：
  • 层内边：M * (K+1)。
  • 层间边：这取决于模式。模式一中，每条原边都可能对应一条层间边，所以最多M * K条。模式二中，可能每个点都能向其他所有点连层间边，理论最坏可达N^2 * K条，通常需要根据题目数据范围判断是否可行，或进行优化（例如，层间边只连接少数特定点）。
• 总复杂度：使用堆优化Dijkstra算法，时间复杂度为O((总边数 + 总点数) * log总点数)。当K不大（通常K <= 10）时，N*(K+1)和M*(K+1)仍在可接受范围内。但如果K很大（比如K = N），直接构建分层图会导致节点和边数爆炸，此时可能需要结合动态规划等其他思想。

实操心得：在竞赛或面试中，看到N, M <= 1e5, K <= 10这样的数据范围，就要条件反射地想到分层图最短路。这是一个非常强烈的信号。

3. 算法实现与代码模板详解

理论清晰了，我们来动手实现。下面以最经典的“有 K 次机会将一条边权值变为 0”为例，给出一个完整的、带有详细注释的 C++ 模板。我们使用邻接表存图，并采用堆优化Dijkstra算法。

3.1 数据结构定义与图构建

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> pli; // pair<距离, 节点编号>，用于优先队列 const int MAXN = 100005; // 原图最大节点数 const int MAXK = 11; // 最大使用次数，通常K较小 const ll INF = 1e18; int n, m, k; // n:节点数， m:边数， k:最大使用次数 int start, target; // 起点，终点 // 分层图节点总数为 n * (k+1) // 我们定义一个编码函数，将二维状态 (节点id, 使用次数) 映射为一维编号 inline int encode(int node, int level) { return level * n + node; } vector<vector<pli>> graph; // 分层图的邻接表， graph[u] = vector<{v, w}> void buildLayeredGraph() { int totalNodes = n * (k + 1); graph.resize(totalNodes); for (int i = 0; i < m; ++i) { int u, v; ll w; cin >> u >> v >> w; u--; v--; // 如果输入是1-based，转为0-based // 构建每一层内的边（正常边） for (int lvl = 0; lvl <= k; ++lvl) { int from = encode(u, lvl); int to = encode(v, lvl); graph[from].emplace_back(to, w); // 双向边 graph[to].emplace_back(from, w); // 如果是无向图 // 如果是有向图，则只加一条 // graph[from].emplace_back(to, w); } // 构建层间边（使用特殊能力的边） // 从第 lvl 层的 u， 到第 lvl+1 层的 v， 代价为 0（免费） for (int lvl = 0; lvl < k; ++lvl) { // 注意 lvl < k，因为第k层不能再用了 int from = encode(u, lvl); int to = encode(v, lvl + 1); graph[from].emplace_back(to, 0); // 同样，如果是无向图，也需要考虑反向使用能力的情况 int from_rev = encode(v, lvl); int to_rev = encode(u, lvl + 1); graph[from_rev].emplace_back(to_rev, 0); } } }

关键点解析：

1. 编码函数encode：这是管理分层图节点的关键。将二维状态(node, level)映射到一维整数，方便用数组存储距离和使用邻接表。这是一种非常高效且不易出错的方式。
2. 层内边循环：遍历所有层(0...k)，在每一层都添加原图的边。这保证了在任何使用次数状态下，都可以进行正常移动。
3. 层间边循环：遍历0到k-1层，从当前层的u向下一层的v连一条权值为0的边。这代表了在u点，对通往v的这条边使用一次免费机会。注意循环边界是lvl < k，因为第k层已经用完了所有机会，不能再向外连层间边。
4. 无向图处理：对于无向图，正常边和层间边都需要添加双向边。这意味着你可以在u对u->v边使用能力，也可以在v对v->u边使用能力，两者是独立的。

3.2 最短路求解与答案获取

图建好后，问题就变成了在这个totalNodes个节点的图上跑最短路。

ll layeredDijkstra() { int totalNodes = n * (k + 1); int source = encode(start, 0); // 起点状态：0号节点，第0层 vector<ll> dist(totalNodes, INF); vector<bool> visited(totalNodes, false); priority_queue<pli, vector<pli>, greater<pli>> pq; // 小顶堆 dist[source] = 0; pq.emplace(0, source); while (!pq.empty()) { auto [curDist, curNode] = pq.top(); pq.pop(); if (visited[curNode]) continue; visited[curNode] = true; // 标准的Dijkstra松弛操作 for (auto &[nxtNode, weight] : graph[curNode]) { if (dist[nxtNode] > curDist + weight) { dist[nxtNode] = curDist + weight; pq.emplace(dist[nxtNode], nxtNode); } } } // 答案：在所有层的终点中，取距离最小值 ll ans = INF; for (int lvl = 0; lvl <= k; ++lvl) { int targetState = encode(target, lvl); ans = min(ans, dist[targetState]); } return ans; }

关键点解析：

1. 起点初始化：起点是(start, 0)，即起点城市，且尚未使用任何特殊能力。
2. 最短路过程：和普通的堆优化Dijkstra完全一致，没有任何特殊之处。这正是分层图思想的优美之处——将复杂的状态决策问题，规约到了经典算法上。
3. 答案提取：我们的目的地是target城市，但我们不关心到达时用了多少次能力。因此，我们需要检查所有层的target节点，即状态(target, 0),(target, 1), ...,(target, k)，它们对应的最短距离dist，其中的最小值就是全局最优解。因为可能不用完K次机会就能得到更短的路径。

3.3 内存优化技巧：隐式建图与动态规划视角

当K或N较大时，显式地构建出graph向量可能会占用过多内存。我们可以采用“隐式建图”的思路，即在Dijkstra的松弛过程中，动态地生成下一层状态。

ll dijkstraWithoutExplicitGraph() { // dist[node][level] 表示到达 node 节点，使用了 level 次能力的最短距离 vector<vector<ll>> dist(n, vector<ll>(k+1, INF)); // 优先队列元素： (距离, 节点, 使用次数) using State = tuple<ll, int, int>; priority_queue<State, vector<State>, greater<State>> pq; dist[start][0] = 0; pq.emplace(0, start, 0); while (!pq.empty()) { auto [curDist, curNode, curLevel] = pq.top(); pq.pop(); if (curDist > dist[curNode][curLevel]) continue; // 不是最优解，跳过 // 松弛操作1：走正常边（同层移动） for (auto &[nxtNode, weight] : originalGraph[curNode]) { ll newDist = curDist + weight; if (newDist < dist[nxtNode][curLevel]) { dist[nxtNode][curLevel] = newDist; pq.emplace(newDist, nxtNode, curLevel); } } // 松弛操作2：使用一次特殊能力（向下一层移动） if (curLevel < k) { for (auto &[nxtNode, weight] : originalGraph[curNode]) { // 假设使用能力后，这条边代价为0 ll newDist = curDist + 0; // 这里是0，也可以是其他值如 weight/2 int newLevel = curLevel + 1; if (newDist < dist[nxtNode][newLevel]) { dist[nxtNode][newLevel] = newDist; pq.emplace(newDist, nxtNode, newLevel); } } } } ll ans = INF; for (int lvl = 0; lvl <= k; ++lvl) { ans = min(ans, dist[target][lvl]); } return ans; }

这种方法不需要预先构建庞大的graph对象，只需要存储原图originalGraph。在松弛时，根据当前状态(curNode, curLevel)，分别枚举“正常走”和“使用能力走”两种转移。这本质上是一种基于Dijkstra的DP，状态是(节点， 使用次数)，转移方程就体现在两个松弛操作中。它节省了存储层间边的空间，思维上也更贴近动态规划，是处理分层图问题的另一种高效方式，尤其适合K较大的情况。

注意事项：隐式建图时，优先队列需要存储三维信息(距离， 节点， 层数)。同时，dist数组也变成了二维数组dist[node][level]。在判断是否入队时，需要比较的是dist[nxtNode][newLevel]，逻辑比显式建图稍复杂，但更省内存。

4. 经典例题实战与举一反三

光说不练假把式。下面我们通过三道经典例题，来具体看看分层图如何应用，并分析其中的变种和陷阱。

4.1 例题一：标准模板题——[JLOI2011] 飞行路线

题目描述：有N个城市，M条双向航线。每条航线连接两个城市，有一个票价。现在你有一张K次免费搭乘券，可以在乘坐任何航线时使用，使得那次飞行免费。求从起点S到终点T的最小花费。

分析：这就是我们前面一直在讲的“对边操作”的模板题。K次免费机会，每次可以让一条边的权值变为0。

直接套用我们3.1和3.2节的模板即可。注意是无向图，所以建边要建双向。时间复杂度O((M*K) log(N*K))。

代码要点：完全使用模板。起点S和终点T在输入时通常是1-based，记得在encode前减1。

4.2 例题二：状态切换题——[USACO09FEB] Revamping Trails G

这道题和“飞行路线”非常像，但有一个关键区别：免费券的使用对象是路径，而不是单条边？不，仔细读题后发现，其实还是对单条边操作。但它是一个很好的练习，因为数据范围更大 (N=10000, M=50000, K=20)，需要用到我们3.3节提到的隐式建图（DP+Dijkstra）方法来节省空间，否则显式建图边数可能达到M*(K+1) + M*K ≈ 2e6，在栈上或静态数组上可能吃力，用vector邻接表更安全。

解题启示：当K达到20时，显式建图的节点数N*(K+1)=210000，边数约2e6，使用堆优化Dijkstra是可行的，但要注意内存管理。使用隐式DP方法思维难度稍高，但内存更优。在竞赛中，根据数据范围灵活选择。

4.3 例题三：多维分层/条件分层——[ARC061E] すぬけ君の地下鉄旅行

题目描述：这个题难度上了一个台阶。城市地铁系统，每条边属于一家铁路公司。当你乘坐同一家公司的线路连续移动时，费用只计1次（类似于公交的换乘优惠）。但如果换乘到另一家公司，需要额外支付1元。求最小费用。

分析：这不再是简单的“使用K次”，而是状态与上一段使用的公司相关。我们可以将“状态”定义为(当前车站， 上一段使用的公司)。但公司数量很多，直接复制图层会导致图巨大。

分层图变形：

1. 状态设计：我们建立两层（或者说多种状态）的图。一种状态是“在车站u，并且刚刚乘坐的是公司c”。另一种特殊状态是“在车站u，但没有上一段乘坐信息”（例如起点）。
2. 建图：
   • 乘坐同公司线路：从状态(u, c)到状态(v, c)，费用为0。这表示连续乘坐同一家公司。
   • 换乘：从状态(u, c)到状态(u, 无)，费用为0？不对。实际上，当我们到达车站u后，我们可以选择以任何公司为起点开始下一段。更精确的建模是：将“到达车站u”这个事件作为一个节点。从所有(u, c)状态都可以以费用1的代价，转移到“虚拟节点u”。然后从“虚拟节点u”可以以费用0的代价，转移到从u出发的任何线路的初始状态(v, c)（假设边(u,v)属于公司c）。
3. 优化：直接为每个(车站， 公司)建点不可行，因为公司数多。但我们可以利用“同一公司的边是批量处理的”这一特点。对于连接车站u和v、属于公司c的边，我们不在所有(u, c)和(v, c)之间直接连边，而是引入一个“公司节点”(c)。然后连边：u -> (c)(费用1)，(c) -> v(费用0)，以及反向v -> (c),(c) -> u。这样，通过公司节点(c)的路径u -> (c) -> v的总费用就是1，模拟了乘坐公司c的线路。而如果从(c1)走到(c2)，则需要经过车站节点u，并支付换乘费。

这道题的分层图思想体现在将“公司”作为一个维度进行状态分离。它不再是简单的“第几层”，而是根据“上一段乘坐的公司”来划分不同的状态子图。这要求我们对分层图的理解更深入一层：分层图的本质是状态机，层是状态的一种表现形式。当状态不是简单的“使用次数”，而是更复杂的属性时，我们需要设计相应的节点和边来刻画状态转移。

4.4 举一反三：你能想到的其他变种吗？

1. 有代价的使用：不是免费，而是将边权减半，或者变为一个固定值C。只需要修改层间边的权值即可。
2. 多种能力混合：有K1次免费机会，K2次半价机会。状态就需要两维(level1, level2)，图变成三维的“立方体图”。节点数N*(K1+1)*(K2+1)。实现时encode函数需要编码三维状态。
3. 能力有使用条件：只能在某些特定节点使用免费机会。那么只在那些特定节点处，才构建向外的层间边。
4. 求路径方案：在记录最短距离dist的同时，记录pre前驱节点和used到达该状态时使用的能力次数，最后从终点状态反向回溯即可还原路径。

5. 常见陷阱、调试技巧与性能优化

即使理解了原理，实现时依然会踩坑。下面是我在多次实战中总结出的经验。

5.1 常见错误与排查清单

5.2 调试技巧：从小规模数据开始

当你对代码没把握时，最好的方法是构造一个微型的、可以手算的测试用例。

示例：N=3， 边：(1-2, 权5)，(2-3, 权5)。起点1，终点3，K=1（一次免费机会）。

• 手算最优解：对边1-2使用免费，路径为1-(免费)->2-(5)->3，总花费为5。
• 调试：
  1. 打印totalNodes = 3*(1+1)=6。
  2. 打印每个节点的encode结果，例如(1,0)->0,(2,0)->1,(3,0)->2,(1,1)->3,(2,1)->4,(3,1)->5。
  3. 打印邻接表，重点看层间边：检查节点0 ((1,0)) 是否有一条权0的边指向节点4 ((2,1))？节点1 ((2,0)) 是否有一条权0的边指向节点5 ((3,1))？以及它们的反向边。
  4. 运行 Dijkstra，打印最终的dist数组。看dist[5]（即(3,1)）是否为5。

通过这样小数据的验证，可以快速定位是建图错误还是算法实现错误。

5.3 性能优化实践

1. 使用vector和emplace_back：避免使用list或静态数组，vector的缓存友好性更好。emplace_back避免临时对象拷贝。
2. 使用priority_queue默认的大顶堆，但存储(距离， 节点)时使用greater比较函数，或者存储负距离。前者更清晰。
3. encode函数声明为inline：这是一个频繁调用的小函数，内联可以提升性能。
4. 使用long long：最短路权值累加很容易超过int范围，除非题目明确说明，否则一律用long long。
5. 隐式建图以节省内存：如前所述，当K较大或内存紧张时，dist[node][level]+ 动态松弛的方案是首选。
6. 如果K非常小（比如K<=5），且N很大，有时可以跑K+1次普通的 Dijkstra 来模拟，每次跑完后更新“免费边”的集合。但这通常不如分层图直观和通用。

分层图最短路是一个将动态规划与图论算法完美结合的典范。它教会我们，面对复杂的状态依赖问题时，不妨尝试“升维”——将状态作为图的一部分，从而利用成熟的经典算法来解决问题。掌握它，不仅能解决一大类算法竞赛题目，更能提升你将现实问题抽象为图论模型的能力。下次遇到“有限制条件的最短路”时，不妨先想想：能不能给它分个层？