P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
题目背景
注：对于 \(k\) 短路问题，A* 算法的最坏时间复杂度是 \(O(nk \log n)\) 的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 \(O((n+m) \log n + k \log k)\) 的时间复杂度解决 \(k\) 短路问题。详情见 OI-Wiki。
题目描述
iPig 在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig 对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒\(\ldots\)。
iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素\(\ldots\)等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 \(1\) 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 \(N\) 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾\(\ldots\)现在的你呀！
注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。
输入格式
第一行三个数 \(N, M, E\)，表示 iPig 知道的元素个数（元素从 \(1\) 到 \(N\) 编号），iPig 已经学会的魔法个数和 iPig 的总能量。
后跟 \(M\) 行每行三个数 \(s_i, t_i, e_i\) 表示 iPig 知道一种魔法，消耗 \(e_i\) 的能量将元素 \(s_i\) 变换到元素 \(t_i\)。
输出格式
一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
有意义的转换方式共 \(4\) 种：
\(1\to 4\)，消耗能量 \(1.5\)。
\(1\to 2\to 1\to 4\)，消耗能量 \(4.5\)。
\(1\to3\to4\)，消耗能量 \(4.5\)。
\(1\to2\to3\to4\)，消耗能量 \(4.5\)。
显然最多只能完成其中的 \(3\) 种转换方式（选第一种方式，后三种方式任选两个），即最多可以转换 \(3\) 份样本。
如果将 \(E=14.9\) 改为 \(E=15\)，则可以完成以上全部方式，答案变为 \(4\)。
数据规模
占总分不小于 \(10\%\) 的数据满足 \(N \leq 6,M \leq 15\)。
占总分不小于 \(20\%\) 的数据满足 \(N \leq 100,M \leq 300,E\leq100\) 且 \(E\) 和所有的 \(e_i\) 均为整数（可以直接作为整型数字读入）。
所有数据满足 \(2 \leq N \leq 5000\)，\(1 \leq M \leq 200000\)，\(1 \leq E \leq 10 ^ 7\)，\(1 \leq e_i\leq E\)，\(E\) 和所有的 \(e_i\) 为实数。
数据更新日志
- 2010/xx/xx：原版数据；
- 2018/03/02：@kczno1 添加了 一组数据；
- 2018/04/20：@X_o_r 添加了 一组数据；
- 2021/01/08：@LeavingZ 添加了 两组数据。
📌 题目分析
给定数据： * \(N\) 种元素（节点），\(M\) 种单向转化魔法（有向边），总能量 \(E\)。 * 边权（消耗的能量 \(e_i\)）为实数。 * 要求：求从元素 \(1\) 到元素 \(N\) 的所有不同转换路径中，能完整走完的最多路径数量（总能量消耗 \(\le E\)）。
👉 本质： 求有向图的 \(K\) 短路 (K-th Shortest Path) 并在总长度不超过 \(E\) 的限制下求最大的 \(K\)。
👉 类型： A* 算法 (A-Star Search) / 可持久化可并堆（Eppstein 算法）。
🧠 解题思路
1️⃣ 为什么不能用普通的 Dijkstra？
Dijkstra 只能求出“第 \(1\) 短”的路径，一旦某个节点被确定了最短路，它就不再更新。 但在本题中，我们需要寻找第 \(1\) 短、第 \(2\) 短、第 \(3\) 短……一直到能量 \(E\) 被耗尽。这意味着一个节点可能会被多次经过，形成不同的方案，我们需要一种算法能按路径长度递增的顺序依次给出所有路径。
2️⃣ A* 算法的核心思想
A 算法是广度优先搜索（BFS）结合启发式函数的升级版。 在 A 搜索中，我们使用一个优先队列（小顶堆），优先级由一个估价函数决定： $\(f(x) = g(x) + h(x)\)$ * \(g(x)\)：从起点 \(1\) 走到当前节点 \(x\) 的实际已消耗能量。 * \(h(x)\)：从当前节点 \(x\) 走到终点 \(N\) 的预计最少消耗能量。 * \(f(x)\)：经过节点 \(x\) 的整条路径的预估总能量。
优先队列每次弹出 \(f(x)\) 最小的状态进行扩展。由于我们的 \(h(x)\) 绝对不会大于实际最短距离，所以第 \(k\) 次走到终点 \(N\) 时，必然就是全局的第 \(k\) 短路！
3️⃣ 如何计算极其精准的 \(h(x)\)？
如何知道每个点到终点 \(N\) 的最少能量？ 神仙操作：反向建图。 把所有边的方向反转，以终点 \(N\) 为起点跑一次标准的 Dijkstra，求出的就是每个节点到终点 \(N\) 的完美最短距离！这就是我们 A* 算法中完美且最优的 \(h(x)\)。
4️⃣ 极限剪枝
这道题有一个天赐的条件：总能量 \(E\) 是固定的。 因此，在 A* 扩展节点时，如果发现 \(f(x) = g(x) + h(x) > E\)，说明这条路径就算接下来的路走得再完美，总消耗也会大于 \(E\)。这种状态直接丢弃，不加入队列。这能极大程度地防止优先队列撑爆！
💻 C++代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const double INF = 1e18;
const int MAXN = 5005;
struct Edge {
int to;
double weight;
};
vector<Edge> adj[MAXN]; // 正向图，用于 A*
vector<Edge> rev_adj[MAXN]; // 反向图，用于求 h(x)
double h[MAXN]; // h[x] 存储 x 到终点 N 的最短距离
// 优先队列优化 Dijkstra，求 h(x)
void dijkstra(int start, int n) {
fill(h, h + n + 1, INF);
h[start] = 0;
// pair<double, int> 默认按 double 从小到大排序
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
double d = top.first;
int u = top.second;
if (d > h[u]) continue;
for (const auto& edge : rev_adj[u]) {
int v = edge.to;
double w = edge.weight;
if (h[u] + w < h[v]) {
h[v] = h[u] + w;
pq.push({h[v], v});
}
}
}
}
// A* 搜索状态节点
struct State {
int u;
double g, f;
// 小顶堆，f 越小优先级越高
bool operator>(const State& other) const {
return f > other.f;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
double E;
if (!(cin >> n >> m >> E)) return 0;
for (int i = 0; i < m; i++) {
int u, v;
double w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
rev_adj[v].push_back({u, w});
}
// 1. 在反向图上跑 Dijkstra，求出所有点到终点 N 的最短路 h(x)
dijkstra(n, n);
// 如果起点无法到达终点，直接输出 0
if (h[1] == INF) {
cout << 0 << "\n";
return 0;
}
// 2. 正向 A* 搜索 K 短路
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({1, 0, h[1]}); // 起点 1，g=0, f=h[1]
int ans = 0;
while (!pq.empty()) {
State curr = pq.top();
pq.pop();
// 到达终点
if (curr.u == n) {
if (E >= curr.g) {
E -= curr.g; // 消耗能量
ans++; // 完成一种方式
continue; // 题目要求一旦到终点，样本转化结束，不继续向下扩展
} else {
// 如果当前弹出的完整路径消耗已经大于剩余能量 E，后续的必定更大，直接结束
break;
}
}
// 扩展相邻节点
for (const auto& edge : adj[curr.u]) {
int v = edge.to;
double w = edge.weight;
double next_g = curr.g + w;
double next_f = next_g + h[v];
// 剪枝：如果预估总消耗已经大于初始总能量 E，直接抛弃
if (next_f <= E + 1e-8) {
pq.push({v, next_g, next_f});
}
}
}
cout << ans << "\n";
return 0;
}
⚠️ 易错点
- A* 队列爆炸 (MLE)： 普通的 A* 如果不加限制，很容易因为扩展了太多无用节点把内存撑爆。这里加入了
next_f <= E + 1e-8这个极限剪枝，是防止 MLE 的绝对核心。 - 终点不可达特判： 如果图是不连通的（或者不存在 \(1 \to N\) 的路径），跑完反向 Dijkstra 后 \(h[1]\) 会是无穷大。如果不加特判直接塞入 A* 队列，会导致逻辑错乱。
- 转化过程结束的理解： 题目提到：“一但转化到目标元素，则一份样本的转化过程结束”。这意味着在 A 出队时，只要当前节点是终点 \(N\)，扣除能量并让
ans++后，千万不要再将它的出边压入队列*（用continue跳过扩展）。
🚀 一句话总结
🔥 补充：A* 的末日危机与 Eppstein 算法
正如题目背景所吐槽的，A 算法在 \(K\) 短路问题上存在一个致命弱点：它的最坏时间复杂度是指数级的 \(O(NK \log N)\)。 如果出题人恶意构造一个带有大量长度相近的“平行边”或“交错链”的图，A 算法会被迫把所有的组合全部塞进优先队列，瞬间 TLE（超时）甚至 MLE（内存超限）。
降维打击的终极解法：Eppstein 算法 (基于可持久化可并堆) 真正的 \(O((N+M)\log N + K \log K)\) 级别解法非常硬核，其核心思想是： 1. 先跑一遍反向最短路树（Shortest Path Tree, SPT）。 2. 将非树边（Deviation Edge）视作是对最短路的“偏离”。每走一条非树边，都会增加一定的额外代价 \(\Delta w\)。 3. \(K\) 短路问题本质上就是寻找这些非树边的最优组合序列。 4. 利用 可持久化左偏树（Persistent Leftist Heap） 极速维护并合并各个节点上的非树边，直接以 \(O(K \log K)\) 的时间抽取出前 \(K\) 个代价最小的偏离方案。
虽然 A* 在本题中依靠剪枝能够勉强通过，但在真正的顶尖算法竞赛（如 NOI 或 ICPC）中遇到被卡数据的 \(K\) 短路时，Eppstein 算法才是唯一的破局之钥。