在图论路径问题中，最短路是一个基础且核心的议题。然而，在诸多场景下，我们关心的并非仅仅是那条唯一的、最优的路径，而是需要一个更广阔的解空间。次短路、第三短路，乃至第 K 短路（K-th Shortest Path, KSP）的需求应运而生。KSP 不仅是基础最短路算法的自然延伸，更是对状态空间搜索、启发式方法以及数据结构运用能力的一次综合考验。

问题定义：路径的界定

在深入算法之前，一个必须首先澄清的基础问题是：我们所讨论的“路径”究竟是什么？在不同的问题背景下，“路径”的定义可能存在微妙但关键的差异，这直接决定了问题的性质、解法乃至其计算复杂度的量级。

通常，一条从顶点到顶点的路径被定义为一个顶点序列，其中 , ，且对于任意，边存在于图的边集中。路径的长度或成本，即为其所经过的边的权值之和。

核心的分歧点在于：路径中的顶点或边是否允许重复？

非严格路径 (Path / Walk): 允许顶点和边在路径中重复出现。例如，在路径中，顶点和边均出现了多次。在这种定义下，如果图中存在正权环，则一个路径可以任意地绕环，从而构造出无限多条长度不同的路径。如果存在零权环，同样可以构造出无限多条长度相同的路径。这是算法竞赛中最常见的 K 短路问题设定。
简单路径 (Simple Path): 要求路径中的所有顶点都是唯一的（除了可能的起点和终点相同，形成一个环路）。这条约束自然地排除了路径中任何环路的出现。

这个定义上的区别至关重要。两类问题的求解难度和算法复杂度有着显著差异：

非严格 K 短路：在非负权图中，该问题已有非常高效的解法。经典算法如 Eppstein 算法 (Eppstein, 1998)，其时间复杂度可达到（该复杂度依赖于使用 Fibonacci 堆等高级数据结构，在竞赛中不常用）。
K 短简单路径：此问题的求解更为复杂。一个普遍的误解是认为该问题是 NP-Hard 的。事实上，在非负权有向图中，寻找 K 短简单路径是多项式时间可解的。代表性算法如 Yen’s 算法 (Yen, 1971)，其时间复杂度为。尽管是多项式时间，但其实现复杂度和运行时间常数相较于非严格版本要大得多。只有在引入负权边（此时问题与检测负环和哈密顿路径等难题相关联）或其他特定约束时，K 短简单路径问题才会变得 NP-Hard。

绝大多数情况下，当我们讨论无特殊说明的“K短路”问题时，我们指的是允许重复顶点和边的“非严格路径”。 本文的核心讨论将围绕这一经典设定展开。

朴素思想的误区

在面对一个新问题时，我们常会尝试从已知算法进行推广。对于 K 短路，一个自然的想法是基于最短路算法进行某种形式的“迭代”或“排除”。

误区一：删除最短路

一个直观的想法是：

找到从到的最短路。
从图中删除所使用的某条边或某个点。
在修改后的图中，再次寻找新的最短路，作为原图的次短路。
重复此过程 K 次。

这个思路是错误的。考虑下图：

(1), (100)
(2), (2)

最短路是，长度为 4。次短路显然是，长度为 101。
如果按照上述思路，我们找到了。如果我们删除边，则新图中的最短路是。但如果我们删除的是边，新图中不再连通。删除哪个元素会产生巨大的影响，且我们无法预知删除哪一个才是正确的选择。

更致命的是，次短路可能与最短路共享大部分边。例如：

(1), (一条长路径，长度 L), (1)
(10), (10)

最短路是，长度 20。
次短路可能是，长度。
第三短路可能是 $'_' allowed only in math modes \to c \to (\text{some_cycle}) \to c \to t$ ，它与最短路共享了所有边。

“删除”的思想破坏了原图的结构，丢失了大量可能构成其他K短路的路径信息，因此不可行。

误区二：简单修改 Dijkstra

Dijkstra 算法的核心是 dist[u] 数组，记录了从源点到顶点的当前已知最短距离。一个自然的想法是将其扩展：dist[u][k]，记录到的第短距离。

在运行 Dijkstra 时，当我们从优先队列中取出状态 (d, u)，并考察边 (u, v) 时，我们会得到一条到的新路径，长度为 d + w(u,v)。在标准 Dijkstra 中，我们检查 d + w(u,v) < dist[v]。在 K 短路的变体中，我们似乎可以将这个新路径长度插入到的一个“最短路候选集合”中，并维持这个集合的大小为 K。

这个想法方向是正确的，但它引出了一个核心问题：我们优先队列中应该存储什么？

标准 Dijkstra 优先队列存储的是 (distance, vertex)，它总是选择当前离源点最近的、尚未确定最短路的顶点进行扩展。这个贪心策略的正确性由 dist[u] 的单调性保证——一旦一个顶点的最短路被确定，它就是最终的、不会再被更新的值。

但在 K 短路中，情况发生了变化。一条当前看起来较长的路径（例如，第5短到达的路径），在经过下一条边后，可能成为到达邻居的一条相对较短的路径（例如，第2短到达的路径）。单纯比较局部的路径长度 d 已经不足以支撑贪心选择了。我们需要一个更具前瞻性的估价标准，来判断哪条“部分路径”最有可能成为最终的全局 K 短路之一。

这正是启发式搜索（Heuristic Search）的用武之地，而 A* 算法为此提供了完美的理论框架。

A* 算法与 K 短路

A* 算法是一种在图形平面上进行路径查找的著名算法，但其本质是一种通用的、可用于任意图结构的最佳路径搜索的算法。它通过引入一个“启发函数”来指导搜索方向，从而显著提高效率。

A* 算法核心思想

A* 算法在扩展搜索节点时，评估每个节点的优先级所依据的函数是：

其中：

是搜索过程中的一个节点（在图搜索中，通常指一个顶点）。
是从起始节点到当前节点的实际代价（路径长度）。
是从当前节点到目标节点的预估代价。这个函数被称为**启发函数 (Heuristic Function)**。

A* 算法的效率和正确性与的设计密切相关。一个关键的性质是**可采纳性 (Admissibility)**。

定义 (可采纳启发函数)：如果对于所有节点，启发函数的值永不高于从到目标节点的实际最小代价（即最短路长度），则称是可采纳的。令为从到目标的真实最短路，则可采纳性意味着。

A 的工作流程:
A 算法使用一个优先队列来存储待访问的节点，队列按照的值进行升序排序。

将起始节点放入优先队列。
当队列不为空时，取出值最小的节点。
如果是目标节点，则搜索成功。
否则，对于的每一个邻居：
- 计算出一条通过到达的新路径，其代价为。
- 如果之前未被访问，或这条新路径更优，则更新的信息，并将放入优先队列。其在队列中的优先级由决定。

当时，A* 算法退化为 Dijkstra 算法。当是可采纳的，A* 算法保证能找到最短路径。设计得越接近真实代价（但不能超过），搜索的剪枝效果就越好，算法效率越高。

将 A* 应用于 K 短路问题

现在，我们将 K 短路的求解过程重新建模为一个在状态空间中的搜索问题。这个状态空间中的“节点”不再仅仅是图中的一个顶点 u，而是一个二元组 (u, d)，表示“当前已经走过一条长度为 d 的路径，并抵达了顶点 u”。我们的目标是在这个隐式的、巨大的状态空间中，找到 K 条通往终点的、总成本最低的路径。

让我们来定义 A* 所需的函数：

状态: 一个 (u, g_u) 对，其中 u 是当前顶点，g_u 是从源点沿某条路径到达 u 的实际已花费代价。
: 对于状态 (u, g_u)，其值就是本身，即从到的已知路径成本。
: 这是 A* 的精髓。对于状态 (u, g_u)，我们需要一个预估其“未来代价”的启发函数。一个完美且可采纳的选择是：从顶点到终点的真实最短路径长度。我们记作。
: 因此，一个状态 (u, g_u) 的总估价为。

这个值的直观意义是：预估的从经由当前路径到达，再从走最短路到达的总路径长度。

由于我们选择的是到的真实最短路，它天然满足可采纳性条件 ( 从到的任意一条路径长度)。因此，基于这个值的搜索，具备一个优美的性质：

核心性质：算法从优先队列中第次取出终点时，所对应的路径就是原图的第短路。

严格证明：A 算法求解 K 短路的正确性*

我们要证明的核心命题是：当 A* 算法第次从优先队列中取出终点的状态时，该状态对应的路径长度，就是从源点到的第短路（允许重复顶点/边）的长度。

为方便论证，我们先定义几个符号：

: 从节点到终点的真实最短路径长度。在我们的算法中，预处理得到的就等于。
: 一条路径的长度。
: A* 搜索过程中，沿着路径到达节点的状态的估价，即。
: 从到的真实的第短路长度。
: 一条长度为的路径。
: 算法第次从优先队列中取出的终点的状态。其对应的路径长度为。

我们的证明目标是：。

我们将使用数学归纳法来证明。

1. 基础情况 (Base Case):

我们要证明，即算法第一次找到的终点路径就是最短路。

设是一条从到的最短路，其长度为。考虑上的任意一个节点，以及从沿到的子路径。
该状态的估价为。
由于是的最短路长度，而从沿到的子路径只是众多路径中的一条，所以。
因此，。
这条不等式意味着，在最短路上的任何一个状态，其值都不会超过最短路本身的长度。
A* 算法维护一个优先队列，并总是取出值最小的节点进行扩展。在算法终止前（或找到前），上的某个状态（或所有状态）必然会进入优先队列。
设是算法第一次从队列中取出的终点状态，其路径长度为。这意味着在取出之前，所有被取出过的状态的值都满足。
假设。这意味着。根据我们之前推导的，在最短路上必然存在某个未被扩展的节点，其值。
这与优先队列的性质相矛盾：一个值更小的节点应该在之前被取出。
因此，假设不成立，必然有。又因为是最短路长度，所以。
综上，。基础情况成立。

2. 归纳步骤 (Inductive Step)

假设对于所有，都有成立。即算法找到的前条终点路径，其长度恰好是的前短路长度。
我们要证明。

设是一条的第短路，长度为。与基础情况类似，对于上的任意节点，其状态的值满足。
这意味着，在算法的某个时刻，路径上的某个状态必然会以一个不大于的值进入优先队列。
设是算法第次从优先队列取出的终点状态。由于优先队列的值单调非递减性，我们有。
**我们首先证明 **。
- 假设。
- 考虑路径。它必然与前条最短路中的至少一条不同。
- 在上的所有状态的值都。因为，所以如果对应的终点状态尚未被发现，那么上一定存在一个未被扩展的节点，其值。
- 这同样与优先队列的性质矛盾，因为应该在之前被取出。
- 因此，假设不成立，必有。
**接着我们证明 **。
- 是第个被从队列中取出的终点状态。它对应一条从的路径，长度为。
- 根据归纳假设，我们已经找到了条不短于的路径，它们的长度分别是。
- 是我们找到的下一条路径的长度。根据 A* 算法的探索机制（它不会遗漏任何可能的路径），这条新发现的路径，其长度必然大于或等于所有已发现路径的长度。
- 因此，路径是在的所有路径中，长度排在前位的一条。根据第短路长度的定义，必然大于或等于。
综合两点，且，因此。

结论

通过数学归纳法，我们证明了对于任意正整数，A* 算法找到的第个终点状态，其路径成本等于真实的第短路长度。证明完毕。

算法流程

基于 A* 的 K 短路算法分为两步：

Step 1: 预处理计算启发函数

为了得到所有点到终点的最短路程，我们需要在反向图 (Reverse Graph) 上，以为源点，运行一次单源最短路算法。

构建反向图 : 对于原图中的每条有向边，其权值为，我们在反向图中添加一条边，权值不变。
运行最短路算法: 在上，从源点开始，运行一次 Dijkstra 算法（如果图中存在负权边但无负环，则使用 SPFA）。这样，我们就得到了到所有其他点的最短距离。在中从到的最短路，等价于在原图中从到的最短路。将这些距离存储在数组 h 中，即 h[u] 就是我们需要的。

Step 2: A 搜索*

执行一个 Dijkstra 算法的变体来进行 A* 搜索。

优先队列: 建立一个最小优先队列 pq。队列中存储三元组 (f, g, u)，分别代表状态的估价、当前实际代价和当前顶点。队列根据值从小到大排序。
计数器: 用一个计数器 cnt[u] 记录顶点被从优先队列中取出的次数。
初始化: 将初始状态 (h[s], 0, s) 放入优先队列。g 值为 0 因为我们刚从出发，f 值为 0 + h[s]。
主循环:
1. 当 pq 不为空时，取出队首元素 (current_f, current_g, u)。
2. 增加 u 的被访问计数 cnt[u]++。
3. 判断终点: 如果 u == t，那么我们找到了一条到达终点的路径，其长度为 current_g。这就是第 cnt[t] 短路。将这个长度记录下来。如果 cnt[t] == K，我们已经找到了全部 K 条最短路，算法可以提前终止。
4. 剪枝: 如果 cnt[u] > K，说明我们已经找到了 K 条以上到达的路径。由于 A* 算法总是优先扩展估价更小的状态，后续再经过的路径其估价通常会更大，不太可能构成全局前 K 短路。这个剪枝对于允许重复顶点的 KSP 是严格安全的（不会错失最优的 K 个解），并且对于包含零权环的图至关重要，可以显著减少状态空间的无谓膨胀。
5. 扩展邻居: 对于 u 的每条出边 (u, v)，权值为 w：
  - 计算出新状态的代价：new_g = current_g + w。
  - 计算出新状态的估价：new_f = new_g + h[v]。
  - 将新状态 (new_f, new_g, v) 压入优先队列 pq。

这个过程本质上是在状态空间图上运行的 Dijkstra 算法，其中值扮演了 Dijkstra 中“距离”的角色。因为我们允许重复访问顶点，所以 cnt[u] 是必要的，以区分到达同一顶点的不同路径。

思考与拓展

负权边与 SPFA

如果图中存在负权边但没有负权环，A* 算法的框架依然适用。但需要进行以下调整：

预处理: 在反向图上，从终点运行 SPFA 算法，计算出启发函数。
A* 搜索: 主循环逻辑不变。值得注意的是，此时计算出的可能为负值，导致估价不再保证单调非负。然而，只要仍然满足一致性条件（对于由 SPFA 计算出的最短路程，此条件成立），A* 算法的正确性依然有保证。算法的底层机制并不依赖于值的非负性，只依赖于其作为“最优估价”的排序能力。

一个更鲁棒的替代方案是先使用 Johnson 算法将所有边权转化为非负，然后再运行基于 Dijkstra 的标准 A* 算法。但由于 Johnson 算法本身就需要一次 SPFA，所以整体的复杂度瓶颈依然在 SPFA。

路径包含环路

需要再次强调，本文讨论的 K 短路算法找到的是允许重复顶点和边的“非严格路径”。

正权环: 当路径包含一个正权环时，算法会自然地将其视为一条新的、更长的路径，并作为一个独立的候选路径进行评估。
零权环: 如果图中存在零权环，算法可能会陷入困境，不断地绕着零权环生成无限多条长度相同的路径。
负权环: 如果存在负权环，则最短路本身无定义，K 短路问题也无从谈起。

应对策略:
对于零权环，我们可以使用计数器剪枝 if (++cnt[u] > K) continue;。这个剪枝是严格安全的，它确保了对于每个中间节点，我们最多只考虑 K 条不同的路径到达它。
进一步讨论: 如果题目要求将“同权但路径不同（例如，绕环次数不同）”的路径视为不同解并全部计数，那么简单的 cnt[u] > K 剪枝就不再适用。此时需要根据题意调整策略，例如将剪枝阈值放宽到一个更大的数（如），或者在状态中额外记录环的使用次数，但这已超出典范 KSP 的范畴。

第 K 短“简单”路径

在非负权有向图中，寻找第 K 短的简单路径（无重复顶点）是一个在多项式时间内可解的问题，而非通常误解的 NP-Hard。只有在引入负权边或添加其他全局约束（如必须经过某些点）后，该问题才会变得 NP-Hard。

解决 K 短简单路径的经典算法是 **Yen’s Algorithm (1971)**。其基本思想是一种迭代式的“偏离-再寻路”策略：

用 Dijkstra 找到最短简单路径。
迭代从 2 到 K：
- 在已找到的第 1 到第条简单路径中，对每一条路径上的每一个节点，都尝试从该节点偏离原始路径。
- 为了强制偏离，需要临时性地从图中移除某些边或点，然后在修改后的图上寻找从偏离点到终点的新最短路。
- 将所有这样生成的候选路径收集起来，从中选出最短的一条，作为第短简单路径。

Yen’s 算法的时间复杂度为。由于其实现相对复杂，且常数较大，在算法竞赛中不常作为直接考点。

替代方法：可持久化数据结构优化

A* 算法从一个全局的视角出发，通过启发函数评估通往终点的“希望”，是解决 K 短路问题最经典和普适的方法。然而，我们也可以从另一个角度思考，即回到我们最初的那个“朴素思想”：为每个点维护一个包含K个最短路径长度的列表。这个思想的瓶颈在于如何高效地实现和更新这个列表。

我们可以将 Dijkstra 算法的 dist[u] 升级。原先 dist[u] 是一个标量，现在我们让它成为一个能够存储 K 个最小值的容器。每次通过边 (u, v) 松弛时，我们不再是简单地比较并替换，而是将新的路径长度 dist[u] + w(u,v) 尝试“插入”到 v 的 K 小值容器中。

数据结构的选择

对于每个顶点，我们需要一个数据结构 D_v，它能：

高效地插入一个新值，复杂度为。
高效地查询当前存储的最大值（为了判断新值是否可以替换之），复杂度为。
高效地删除（弹出）最大值，复杂度为。
维持容器内元素数量不超过 K。

一个**最大堆 (Max-Heap)**，或者 C++ 中的 std::priority_queue，是实现这个功能的理想选择。对于每个顶点，我们维护一个大小不超过 K 的最大堆 D_v。

算法流程

为每个顶点创建一个空的最大堆。
创建一个全局的最小优先队列 PQ，用于 Dijkstra 流程。队列中存放 (d, u)，表示一条长度为的路径到达了顶点。
将源点的一条长度为 0 的路径加入，即 PQ.push({0, s})，同时 D_s.push(0)。
当 PQ 不为空时，取出队首 (d, u)。
如果大于的堆中的最大值（即 d > D_u.top()），说明这条路径 (d, u) 是在我们已经找到的到达 u 的更好路径之后才被处理的，它是一条“冗余”的、更劣的路径，直接跳过。
遍历 u 的所有出边 (u, v)，权值为 w：
- 计算新路径长度 new_d = d + w。
- 考察的最大堆：
  - 如果的大小小于 K，直接将 new_d 插入，并将 (new_d, v) 压入全局优先队列 PQ。
  - 如果的大小等于 K，但 new_d 小于的最大元素（即 new_d < D_v.top()），则说明 new_d 比当前已知到达的 K 条路径中最差的一条要好。于是，弹出的堆顶，将 new_d 插入，并将 (new_d, v) 压入全局优先队列 PQ。

算法结束时，中存储的就是从到的 K 条最短路（如果不满 K 条，则存所有可达路径）。

可持久化堆优化

上述方法存在一个效率问题。每次成功将新路径长度 new_d 插入到的堆时，我们都向全局优先队列 PQ 中压入了 (new_d, v)。这意味着同一条路径 (d,u) 的扩展可能会因为更新了多个邻居，而向 PQ 中加入多个元素。更重要的是，整个算法的松弛次数大大增加。

考虑一个顶点，它有条路径被找到。它会对它的每个邻居产生次松弛尝试。这导致了大量的重复计算。

一个精巧的优化是使用可持久化数据结构，特别是可持久化左偏树 (Persistent Leftist Tree) 或其他可持久化堆。

其思想是将 Dijkstra 与数据结构的操作更紧密地结合。我们不为每个节点维护一个独立的堆，而是让 Dijkstra 的每个状态都指向一个代表路径信息的数据结构版本。

这是一种更为高级的技巧，其核心思想是：

Dijkstra 运行在“决策”上，而非“顶点”上。
每个状态 (d, u) 扩展时，不是去更新邻居 v 的信息，而是基于 u 的路径信息和边 (u, v)，生成一个到 v 的新路径。
同时，我们还可以考虑从 u 的“次优”路径进行扩展。

这种方法通常被称为“可并堆优化K短路”。算法大致如下：

在反图上，从点跑 Dijkstra，得到最短路树。
对于每个点，它不在最短路树上的出边称为“非树边”。每条非树边都提供了一个偏离最短路径的机会。
对于每个点，我们用一个可并堆（例如左偏树）来维护所有从出发、不走最短路树路径、最终到达的“岔路”的候选路径。堆顶是这些岔路中长度增加最少的那条。
初始时，我们将的岔路堆加入一个全局的优先队列。
每次从全局优先队列中取出堆顶代价最小的岔路，这就是下一条更短的路径。假设这条路径是从点偏离的，我们不仅找到了一个新的路径，还需要将的下一个候选岔路，以及从这条新路径的终点开始的岔路合并，放入全局优先队列。

这个方法的实现细节非常复杂，涉及到可并堆的大量操作（合并、插入、删除）。它的优势在于理论复杂度更优，但实现难度和代码复杂度远高于 A* 算法，在竞赛环境中除非是作为模板深熟于心，否则 A* 是更稳妥和实用的选择。

对比 A* 与“K-堆”Dijkstra

在解决非严格 K 短路问题时，两种主流思路——A* 搜索和对 Dijkstra 的直接扩展（我们称之为“K-堆”Dijkstra）——各有其适用场景和优劣。

A* 算法:
- 优点: 思路清晰，是启发式搜索的经典应用。通过一个高质量的启发函数（从各点到终点的最短路），A* 能够进行目的性极强的搜索，极大地剪除了无效的状态扩展，因此在实践中通常具有非常高的效率。其实现复杂度适中，是解决单源单汇 K 短路问题的通用标准方案。
- 缺点: 核心优势依赖于启发函数，因此需要一次反向图上的最短路预处理。这使得它天然地专精于单源单汇 (one-to-one) 的场景。如果问题变为求解从一个源点到所有其他点的 K 短路（one-to-all），A* 算法将需要对每个终点分别运行，效率会变得低下。
“K-堆”Dijkstra:
- 优点: 算法流程是标准 Dijkstra 的自然扩展，无需任何预处理。它在一次运行中，可以计算出从源点到所有其他顶点的 K 短路，完美解决了单源全汇 (one-to-all) 的问题。
- 缺点: 性能开销较大。每个顶点需要维护一个大小为的数据结构（如最大堆），使得每次松弛操作的代价从上升到。全局优先队列中可能容纳的状态数量也远多于标准 Dijkstra。其最坏时间复杂度数量级为，但常数更大，在实践中对于单源单汇问题不占优势。

结论:

两种算法的选择取决于具体的问题模型：

对于最常见的单源单汇 (S-T) K 短路问题，A* 算法是实现难度与运行效率之间平衡点最佳的方案，是竞赛和工程中的首选武器。
对于求解单源全汇 K 短路问题，“K-堆”Dijkstra 的思想则是更直接和有效的选择。

特性	A* 算法	“K-堆”Dijkstra
核心思想	启发式搜索 (Best-First Search)，用 $f = g + h$ 指导方向	Dijkstra 的直接扩展，为每个节点记录 K 个最短距离
问题模型	单源单汇 (One-to-One) K 短路	单源全汇 (One-to-All) K 短路
预处理	需要。需在反向图上运行一次 Dijkstra/SPFA 计算启发函数 `h(u)`。	不需要。直接从源点开始搜索。
时间复杂度	(普通二叉堆实现)
空间复杂度	优先队列大小与 K 和图结构相关，通常较小。	每个节点维护一个大小为 K 的堆，空间开销较大。
实践效率	通常更高。启发函数能有效剪枝，减少无效搜索。	通常更低。常数因子较大，状态扩展更盲目。
实现难度	中等。需要额外实现一次反向图上的最短路。	相对直接。核心是对 Dijkstra 的 `dist` 数组进行升级。
首选场景	求解特定起点到特定终点的 K 短路问题。	需要一次性求出从一个起点到所有其他点的 K 短路。

C++ 实现范例

P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

题目背景

注：对于短路问题，A* 算法的最坏时间复杂度是的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在的时间复杂度解决短路问题。详情见 OI-Wiki。

题目描述

iPig 在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig 对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒。

iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

输入格式

第一行三个数，表示 iPig 知道的元素个数（元素从到编号），iPig 已经学会的魔法个数和 iPig 的总能量。

后跟行每行三个数表示 iPig 知道一种魔法，消耗的能量将元素变换到元素。

输出格式

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

有意义的转换方式共种：

，消耗能量。

显然最多只能完成其中的种转换方式（选第一种方式，后三种方式任选两个），即最多可以转换份样本。

如果将改为，则可以完成以上全部方式，答案变为。

数据规模

占总分不小于的数据满足。

占总分不小于的数据满足且和所有的均为整数（可以直接作为整型数字读入）。

所有数据满足，，，，和所有的为实数。

我们以以本题为例。该题是标准的 K 短路模板，但有一个额外的限制：总路径长度不能超过一个给定的能量值。

题意简述
给定一张个点条边的有向图，一个起点和终点，以及一个能量上限。求从到的、长度不超过的路径有多少条。注意，这里的路径可以重复经过点和边。

解题思路

本题要求在总能量预算内，最大化不同路径的转换次数。最优策略是采用贪心思想：总是选择当前可用的、成本最低的路径进行转换。这本质上是一个 K 短路问题，我们需要按成本从小到大的顺序找出所有路径，直到能量耗尽。

考虑到性能要求，我们采用一种基于可持久化可并堆（左偏树） 的高效算法。其核心思想是将任意路径解构为“最短路 + 一系列偏离”。首先，通过在反向图上运行 Dijkstra，我们计算出所有点到终点的最短距离 ds[u]，并构建出最短路树。

接着，我们通过一种非递归的、基于拓扑序的动态规划方式，为每个节点 u 构建一个可持久化堆 rt[u]。这个堆存储了所有从 u 或其下游节点出发的“偏离”选项，并按偏离的额外成本排序。

最后，主过程模拟 A* 搜索，但状态由一个全局优先队列管理。队列中的每个元素代表一个“偏离序列”的总成本。我们从第 1 短路开始，不断从队列中取出成本最低的路径。如果能量充足，就完成一次转换，并基于当前偏离决策，通过“三叉戟式”扩展（即替换为次优偏离，或在偏离后追加新偏离）生成新的候选路径放入队列，直至能量耗尽。此方法系统地、按最优顺序生成了所有路径，精确地解决了问题。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const double INF = 1e18, EPS = 1e-9;
const int N = 5010, M = 200010, H = 1000010, T = 4200010;

int n, m; double E;
int hg[N], tg[M], ng[M], hr[N], tr[M], nr[M], g_c, r_c;
double wg[M], wr[M], ds[N];
int fa[N]; // fa[u]: u在反向最短路树上的父边索引
bool vs[N];

// 左偏树
int rt[N], pc; // rt[u]: u的偏离堆根, pc: 节点池计数
struct HP { int l, r, d, v; double k; } hp[H]; // l,r:左右子, d:dist, v:偏离终点, k:偏离代价

// 手写小根堆 (用于Dijkstra和主循环)
int pq[T], pqc; // pq: 堆数组, pqc: 堆大小
int kid[T]; double kv[T]; int kc; // kid: 节点ID, kv: 节点值, kc: 节点池计数

void g_add(int u, int v, double w) { ng[++g_c] = hg[u]; tg[g_c] = v; wg[g_c] = w; hg[u] = g_c; }
void r_add(int u, int v, double w) { nr[++r_c] = hr[u]; tr[r_c] = v; wr[r_c] = w; hr[u] = r_c; }

int mk(int v, double k) {
    ++pc;
    hp[pc] = {0, 0, 0, v, k};
    return pc;
}

int cp(int x) {
    ++pc;
    hp[pc] = hp[x];
    return pc;
}

int mg(int x, int y) {
    if (!x || !y) return x | y;
    if (hp[x].k > hp[y].k) swap(x, y);
    int p = cp(x);
    hp[p].r = mg(hp[p].r, y);
    if (hp[hp[p].l].d < hp[hp[p].r].d) swap(hp[p].l, hp[p].r);
    hp[p].d = hp[hp[p].r].d + 1;
    return p;
}

void pq_add(int id, double val) {
    kid[++kc] = id; kv[kc] = val;
    pq[++pqc] = kc;
    int i = pqc;
    while (i > 1 && kv[pq[i]] < kv[pq[i / 2]]) {
        swap(pq[i], pq[i / 2]);
        i /= 2;
    }
}

int pq_pop() {
    int ret = pq[1];
    pq[1] = pq[pqc--];
    int i = 1, j = 2;
    while (j <= pqc) {
        if (j < pqc && kv[pq[j + 1]] < kv[pq[j]]) j++;
        if (kv[pq[i]] <= kv[pq[j]]) break;
        swap(pq[i], pq[j]);
        i = j, j *= 2;
    }
    return ret;
}

void dij() {
    for (int i = 1; i <= n; i++) ds[i] = INF;
    kc = pqc = 0;
    ds[n] = 0;
    pq_add(n, 0);
    while (pqc) {
        int t = pq_pop(), u = kid[t];
        if (vs[u]) continue;
        vs[u] = true;
        for (int i = hr[u]; i; i = nr[i]) {
            int v = tr[i];
            if (ds[v] > ds[u] + wr[i]) {
                ds[v] = ds[u] + wr[i];
                fa[v] = i;
                pq_add(v, ds[v]);
            }
        }
    }
}

void build() {
    kc = pqc = 0;
    for (int i = 1; i <= n; i++) pq_add(i, ds[i]);
    hp[0].d = -1;
    while (pqc) {
        int t = pq_pop(), u = kid[t];
        if (fa[u]) rt[u] = mg(rt[u], rt[tg[fa[u]]]);
        for (int i = hg[u]; i; i = ng[i]) {
            int v = tg[i];
            if (fa[u] != i) {
                rt[u] = mg(rt[u], mk(v, wg[i] + ds[v] - ds[u]));
            }
        }
    }
}

int solve() {
    int ans = 0;
    if(E < ds[1] + EPS) return 0;
    E -= ds[1];
    ans++;
    
    kc = pqc = 0;
    if (rt[1]) pq_add(rt[1], ds[1] + hp[rt[1]].k);
    
    while (pqc) {
        int t = pq_pop(), u = kid[t];
        double w = kv[t];
        if (E < w - EPS) break;
        E -= w;
        ans++;
        if (hp[u].l) pq_add(hp[u].l, w - hp[u].k + hp[hp[u].l].k);
        if (hp[u].r) pq_add(hp[u].r, w - hp[u].k + hp[hp[u].r].k);
        if (hp[u].v && rt[hp[u].v]) pq_add(rt[hp[u].v], w + hp[rt[hp[u].v]].k);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> E;
    for (int i = 0, u, v; i < m; i++) {
        double w; cin >> u >> v >> w;
        if (u != n) g_add(u, v, w), r_add(v, u, w);
    }
    dij();
    build();
    cout << solve() << endl;
    return 0;
}

注：以上代码示例针对具体题目（魔法猪学院），使用了更高级的可持久化可并堆优化，其思路在“可持久化堆优化”一节有概念性介绍。对于更通用的 K 短路问题，基于 A* 的实现会更直观，可参考“模型拓展”部分的代码框架。

深度剖析：A* 算法的正确性与效率根源

在前文中，我们确立了 A* 算法作为解决 K 短路问题的标准武器。其核心在于巧妙地结合了已行进的实际代价和对未来代价的预估。现在，我们需更深入地审视这一框架，理解其为何不仅正确，而且高效。

正确性：为何第 K 次到达终点即为第 K 短路？

A* 算法用于 K 短路的核心性质可以表述为：当算法运行时，第次从优先队列中取出终点的状态时，该状态所对应的路径就是从源点到的第短路。

这一性质的根基在于 A* 算法所处理的节点的值序列的单调性。设是算法第次从优先队列中取出的状态的值。由于优先队列的性质，我们有。

让我们考虑任意一条从到的路径，其长度为。当我们的搜索过程进行到上的任意一个中间节点时，所形成的部分路径的长度为。此时，该状态的估价为。因为我们的启发函数是到的最短路径长度，所以从沿路径的剩余部分到达的实际代价必然大于或等于。因此，有：

这条不等式揭示了一个关键事实：任何一条完整路径的长度，是其在 A* 搜索过程中所有中间状态值的上界。

现在，假设我们第次从优先队列中取出一个终点状态。此时，。这意味着我们找到了一条长度为的路径。根据值的单调性，这是我们找到的第个解。

是否存在一条尚未被发现的、比更短的路径？
假设存在这样一条路径，其长度。那么根据上面的不等式，在上的任何一个状态的值都小于等于。这意味着上的所有状态的值都小于。因此，在优先队列中，上的状态（特别是接近终点的状态）应该比我们当前取出的这个终点状态更早被处理。这与我们现在才找到第个解相矛盾。

因此，当第次取出终点时，其路径长度必然是第短的。这个论证虽然不完全严谨，但抓住了 A* 求解 K 短路问题的核心逻辑：它以一种最优优先的方式，按估价成本从小到大的顺序探索整个状态空间，确保了找到解的顺序即为解的优劣顺序。

启发函数的一致性 (Consistency)

除了可采纳性 ()，启发函数还有一个更强的性质，称为一致性或单调性。

**定义 (一致性启发函数)**：对于任意节点和它的任意一个后继节点，启发函数满足以下条件：

其中是边的权值。

这个性质在几何上等价于三角不等式。当我们用于 K 短路的启发函数是到终点的真实最短路程时，这个性质是天然满足的。因为从到的最短路程，不可能比“先从走到，再从走最短路到 ”的路线更长。

一致性是一个非常好的性质。它保证了 A* 算法所找到的任意节点的第一条路径就是到的最短路径（在标准 A* 中）。在 K 短路的上下文中，它确保了值的非递减性，是算法正确性的基石。如果一个启发函数是可采纳但非一致的，A* 仍然能保证找到最优解，但可能会重复扩展某些节点，效率降低。幸运的是，在 K 短路这个经典应用场景中，我们使用的启发函数是“完美”的，既可采纳又一致。

模型拓展：当 K 短路遇上约束

纯粹的 K 短路问题在算法设计中并不算高频。其更大的价值在于，它提供了一个强大的框架来解决一类更广泛的“带约束的次优路径”问题。这类问题的核心在于，路径的选择不仅受长度影响，还需满足额外的条件。解决方法通常是在 A* 的状态定义中加入新的维度来刻画这些约束。

案例一：带限制资源消耗的 K 短路

问题背景：
在一张图中，边被分为两类：普通边和特殊边（例如，需要消耗特定资源的“传送门”）。给定起点，终点，整数和资源上限，求从到的、使用特殊边不超过次的第短路。

建模思路：
这个问题的关键在于，路径的合法性不仅取决于其长度，还取决于已使用的特殊边数量。因此，标准的状态 (u, g) 已经不足以描述搜索的进展。我们需要将已用资源量也纳入状态中。

状态定义: 一个三元组 (u, c, g)，表示当前到达顶点 u，已经使用了 c 条特殊边，总路径长度为 g。
A 搜索状态*: 优先队列中存储 (f, g, u, c)。
启发函数 : 对于状态 (u, c, g)，我们需要的启发函数是预估从 u 到 t 的最小未来代价。最直接且保证可采纳的启发函数，依然是忽略附加约束的最小代价，即到的普通最短路程。因为任何一条满足约束的从到的路径，其长度必然不会小于不考虑任何约束的最短路。
值: 。
剪枝与终止:
- 当从 u 扩展到 v 经过一条特殊边时，新的状态中资源消耗量 c 会加一。如果 c > C，则这条路径非法，不应加入优先队列。
- 用一个计数器 cnt[t] 记录到达终点 t 的次数。当 cnt[t] == K 时，找到答案。
- 为了优化，可以用 vis[u][c] 记录到达状态 (u,c) 的次数，如果次数超过也可以剪枝，因为我们不太可能需要超过条路径到达同一个中间状态。

代码实现

题意简述
给定个点条边的有向图，每条边有一个权值和一个类型（0为普通，1为特殊）。求从到的路径中，使用特殊边不超过次的第短路长度。若不存在或不足条，输出 -1。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005, C_MAX = 11;
const ll INF = 1e18;

int n, m, c, k;

struct Edge {
    int to, nxt, type;
    ll w;
};

vector<Edge> g[N], rg[N]; // 原图与反图

void add(int u, int v, ll w, int t) {
    g[u].push_back({v, 0, t, w}); // nxt is not used with vector
    rg[v].push_back({u, 0, t, w});
}

ll d[N]; // 预处理 h(u)
bool vis[N];

void pre() { // 在反图上跑 Dijkstra
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    d[n] = 0;
    pq.push({0, n});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;

        for (const auto& edge : rg[u]) {
            int v = edge.to;
            ll w = edge.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

struct Node {
    int u, c;
    ll g, f;
    bool operator>(const Node& o) const {
        return f > o.f;
    }
};

int cnt[N]; // 仅用于统计到达终点的次数

ll as() {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    if (d[1] == INF) return -1;
    pq.push({1, 0, 0, d[1]});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        
        int u = cur.u;
        int uc = cur.c;
        ll ug = cur.g;

        if (u == n) {
            cnt[n]++;
            if (cnt[n] == k) {
                return ug;
            }
        }
        
        // 扩展
        for (const auto& edge : g[u]) {
            int v = edge.to;
            int type = edge.type;
            ll w = edge.w;
            
            int vc = uc + type;
            if (vc > c) continue; // 资源超限

            if (d[v] == INF) continue; // 无法到达终点

            ll vg = ug + w;
            ll vf = vg + d[v];
            pq.push({v, vc, vg, vf});
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> c >> k;
    for (int i = 0; i < m; ++i) {
        int u, v, w, t;
        cin >> u >> v >> w >> t;
        add(u, v, w, t);
    }

    pre();
    cout << as() << endl;

    return 0;
}

时间复杂度: 预处理 Dijkstra 是。A* 搜索的状态空间大小变为了。每次从优先队列取出并扩展的复杂度是，其中是出度。总的来说，优先队列中的状态数会与和相关。粗略上界为，但实践中由于 A* 的剪枝效果，性能会好很多。
空间复杂度: 存图，A* 优先队列最坏情况可达。

这个例子展示了 K 短路问题解决范式的强大扩展性。通过将约束条件编码到状态中，我们可以将一个复杂的约束优化问题转化为在扩展状态图上的标准 A* 搜索问题。

案例二：隐式图上的 K 短路

A* 搜索的威力远不止于处理显式给出的图。在很多问题中，图的节点和边是由问题的规则隐式定义的。K 短路框架同样适用于这类问题。

问题背景：
在一个的网格中，有些格子是障碍物。从一个起点 (sx, sy) 出发，每次可以移动到上、下、左、右四个相邻且非障碍的格子，每次移动的代价为 1。求从起点到终点 (tx, ty) 的第短路径长度。

建模思路:
这是一个在隐式图上求 K 短路的问题。

节点: 网格中的每个合法坐标 (x, y) 都是图的一个节点。
边: 如果格子 (x1, y1) 和 (x2, y2) 相邻且均非障碍，则它们之间存在一条权值为 1 的双向边。
状态: A* 搜索的状态是 (g, x, y)，表示以代价 g 到达了 (x, y)。
启发函数 : 从 (x, y) 到终点 (tx, ty) 的预估代价。一个经典且可采纳的启发函数是曼哈顿距离: 。因为每次移动最多使曼哈顿距离减少 1，所以这是到达终点所需步数的下界。
值: 。

算法流程与标准 K 短路完全一致，只需将图的遍历从“访问邻接表”改为“计算四个相邻坐标并判断合法性”。

代码实现

题意简述
在网格中，给定起点终点和障碍物，求第短路。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005;

int n, m, k;
char g[N][N]; // 地图
int sx, sy, tx, ty;

struct Node {
    int x, y;
    ll g, f;
    bool operator>(const Node& o) const {
        return f > o.f;
    }
};

int h(int x, int y) { // 曼哈顿距离
    return abs(x - tx) + abs(y - ty);
}

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

map<pair<int, int>, int> cnt; // 统计到达 (x,y) 的次数

ll as() {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({sx, sy, 0, (ll)h(sx, sy)});
    
    int fcnt = 0; // 找到终点的次数

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        int x = cur.x, y = cur.y;
        ll gv = cur.g;
        
        if (x == tx && y == ty) {
            fcnt++;
            if (fcnt == k) {
                return gv;
            }
        }

        cnt[{x, y}]++;
        if (cnt[{x, y}] > k) continue; // 剪枝：到达同一点次数过多

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] != '#') {
                ll ng = gv + 1;
                ll nf = ng + h(nx, ny);
                pq.push({nx, ny, ng, nf});
            }
        }
    }
    return -1;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 'S') { sx = i; sy = j; g[i][j] = '.';}
            if (g[i][j] == 'T') { tx = i; ty = j; g[i][j] = '.';}
        }
    }

    cout << as() << endl;

    return 0;
}

时间复杂度: 状态空间是。A* 搜索的复杂度与优先队列大小和操作次数有关。每个点最多被有效访问次，每次扩展 4 个方向。复杂度近似为。
空间复杂度: 用于存储地图和 cnt 映射。优先队列大小也与相关。

这两个案例揭示了 K 短路问题解决思路的普遍性：识别状态，定义转移，设计启发，套用 A*。 问题的变化万变不离其宗，关键在于将具体问题抽象为状态空间图上的搜索。

核心陷阱与注意事项

在实现 K 短路算法时，一些细节问题可能导致错误或低效。

零权环的处理

A* 算法允许路径中重复经过顶点和边。如果图中存在一个零权环，会发生什么？
假设有一条路径，其中是一个零权环。算法在找到的路径后，可以绕这个环任意圈，每绕一圈，路径长度不变，但得到了一条新的、不同的路径。这将产生无限多条等长的路径。

如果问题要求找出前 K 短路，而这 K 条路径因为零权环的存在而长度相同，A* 算法会不断地从优先队列中取出这些因绕环而产生的、g 值相同但路径不同的状态，最终可能导致超时或内存溢出。

应对策略:
在 A* 搜索中加入一个对访问次数的计数器 cnt[u]，记录顶点 u 被从优先队列中取出的次数。当 cnt[u] 超过一个阈值时（通常是），就停止从这个顶点进行扩展。

if (++cnt[u] > k) continue;

这个剪枝的原理是：我们已经找到了到达 u 的条不同路径。由于 A* 总是优先扩展值更小的状态，后续再经过 u 的路径，其估价很可能已经高于当前找到的全局前短路的估价了。这是一种非常有效的启发式剪枝，对于处理零权环导致的无限路径问题至关重要，并且在大多数情况下不会丢失正确解。如果题目明确要求区分并计数所有等长但不同的路径，这个上限可以适当放宽，例如设置为。

浮点数精度

当边权为浮点数时，所有比较操作都必须考虑精度问题。

dist[v] > dist[u] + w 应写成 dist[v] > dist[u] + w + EPS (其中 EPS 是一个很小的正数，如 1e-9)。
在优先队列的比较函数中 f > o.f 应写成 f - o.f > EPS。

忽略精度问题是浮点数权值图论问题中最常见的错误之一。

整型溢出

K 短路的路径长度可能远大于单条边的权值。如果边权较大，即使不大，总路径长度 g 也很容易超过 int 的范围。在整个算法中，所有存储路径长度的变量（g, f, d 数组等）都应使用 long long 类型。

再进一步：K 短路与动态规划的融合

K 短路问题在更高阶的应用中，常常与动态规划的思想结合。当边的代价不仅是常数，而是依赖于路径历史时，问题就演变成了在状态图上的最短路/K短路问题，而这个状态图本身就是 DP 状态的集合。

问题背景:
“变色龙”问题。在一张图上，每条边有一个颜色。一只变色龙从走到。它走的路径必须满足颜色交替出现的规则，例如 red -> blue -> red -> ...。路径的起始颜色不限。求满足此规则的第短路。

建模分析:
路径的合法性取决于上一条边的颜色。因此，到达一个顶点 u 是不够的，我们还必须知道“是经由什么颜色的边到达 u 的”。

DP 状态 / 图节点: 将原图的每个节点 u 拆分成多个状态节点。例如，如果颜色有 C 种，可以拆分成 (u, color_1), (u, color_2), ...。状态 (u, c) 表示“变色龙刚刚走了一条颜色为 c 的边，并到达了 u”。
状态转移 / 图的边: 如果原图中存在一条颜色为 c2 的边 (u, v)，并且规则允许从颜色 c1 转换到 c2，那么就在扩展图中添加一条从 (u, c1) 到 (v, c2) 的边，权值与原边相同。
求解: 在这个新构建的、大小为的状态图上，问题被转化为了一个标准的 K 短路问题。源点需要特殊处理：可以从经过任意颜色的第一条边出发，所以可以将所有可能的起始状态 (v, c)（其中 (s,v) 是颜色为 c 的出边）作为多源点，或者设立一个超级源点连接它们。

这个例子完美诠释了 DP 和图论的结合。DP 的状态定义了图的节点，DP 的转移方程定义了图的边。而 K 短路算法（A*）则是在这个由 DP 关系构成的隐式图上进行的高效搜索工具。

K 短路思想的延伸:
这种“将约束/历史信息加入状态”的思想，是解决复杂路径问题的通用范式。无论是要求路径长度奇偶性、经过特定节点集合、满足某种序列模式，其本质都是通过扩展状态空间，将复杂的约束“内化”为图结构的一部分，从而将问题转化为我们熟悉的模型。K 短路提供了一个寻找“次优解集合”的强大引擎，而建模能力则决定了我们能用这个引擎解决多复杂的问题。

写在最后

K 短路问题（KSP）是图论算法中一个承上启下的重要主题。它不仅是基础最短路算法的自然延伸，更是通向更广阔的状态空间搜索、启发式方法和动态规划建模的桥梁。

问题定义：明确了“非严格路径”与“简单路径”的根本区别，以及它们在复杂度上的巨大差异。
**核心算法 A***：深入剖析了 A* 算法如何通过“实际代价+未来预估”的启发式思想，高效且正确地按顺序找出 K 条最短路。
方法对比：比较了 A* 算法与“K-堆”Dijkstra，明确了它们分别适用于单源单汇和单源全汇的场景。
模型拓展：展示了如何通过扩展状态定义，将 A* 框架应用于带约束问题和隐式图问题，体现了其强大的通用性。

掌握 K 短路，不仅仅是学会一个模板。更重要的是，通过它，我们可以建立起一种解决“带约束的最优/次优路径”问题的系统性思维方法：将具体问题抽象为状态空间图，将求解过程看作是图上的智能搜索。