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

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

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

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

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

输入格式
第一行三个数 N , M , E N, M, E N,M,E，表示 iPig 知道的元素个数（元素从 1 1 1 到 N N N 编号），iPig 已经学会的魔法个数和 iPig 的总能量。

后跟 M M M 行每行三个数 s i , t i , e i s_i, t_i, e_i si​,ti​,ei​ 表示 iPig 知道一种魔法，消耗 e i e_i ei​ 的能量将元素 s i s_i si​ 变换到元素 t i t_i ti​。

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

输入输出样例
输入 #1

4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

输出 #1

3

所有数据满足 2 ≤ N ≤ 5000 2 leq N leq 5000 2≤N≤5000， 1 ≤ M ≤ 200000 1 leq M leq 200000 1≤M≤200000， 1 ≤ E ≤ 1 0 7 1 leq E leq 10 ^ 7 1≤E≤107， 1 ≤ e i ≤ E 1 leq eileq E 1≤ei≤E， E E E 和所有的 e i e_i ei​ 为实数。
问题描述：解决边权为正的有向图两点之间非严格第 k k k 短路径的长度。

A ∗ A^* A∗优化算法
采用Dijkstra最短路思想，每次扩展最短的路径，第 k k k 次到达终点时的路径长度即为第 k k k 短路的长度。
由于算法相当于同时进行 k k k 次单元最短路，时间和空间都可能会超限，因此 预处理每个点到终点的最短距离作为估价函数，利用 A ∗ A^* A∗ 算法优化。复杂度为 O ( n k log ⁡ n ) O(nklog n) O(nklogn)。

#include<bits/stdc++.h>#define sd(a) scanf("%lf",&a)
#define repi(i, a, b) for(register int i=a;i<=b;++i)
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 5e3 + 10, M = 2e5 + 10;
int n, m;
int head[N], ver[M << 1], Next[M << 1], tot;
double edge[M << 1], re[M << 1];
int rh[N], rv[M << 1], rn[M << 1], rt;
double f[N];
int v[N];
double e;inline void add(int x, int y, double z) {ver[++tot] = y;edge[tot] = z;Next[tot] = head[x];head[x] = tot;
}inline void add_r(int x, int y, double z) {rv[++rt] = y;re[rt] = z;rn[rt] = rh[x];rh[x] = rt;
}inline void read() {n = qr(), m = qr(), sd(e);for (int i = 1; i <= m; i++) {int x = qr(), y = qr();double z;sd(z), add(x, y, z), add_r(y, x, z);}
}void dijkstra() {repi(i, 1, n)f[i] = 1e9;priority_queue<pair<double, int> > q;f[n] = 0;q.push({0, n});while (!q.empty()) {int x = q.top().second;q.pop();if (v[x])continue;v[x] = 1;for (int i = rh[x]; i; i = rn[i]) {int y = rv[i];double z = re[i];if (f[y] > f[x] + z) {f[y] = f[x] + z;q.push({-f[y], y});}}}
}int astar() {memset(v, 0, sizeof(int) * (n + 1));priority_queue<pair<double, pair<double, int>>> q;q.push({-f[1], {0, 1}});while (!q.empty()) {int x = q.top().second.second;double d = q.top().second.first;q.pop();if (x == n) {if (e < d)return v[n];++v[n], e -= d;}for (int i = head[x]; i; i = Next[i])if (d + edge[i] + f[ver[i]] <= e)q.push({-(d + edge[i] + f[ver[i]]), {d + edge[i], ver[i]}});}return v[n];
}int main() {read();dijkstra();printf("%dn", astar());return 0;
}

即便利用 A ∗ A^* A∗ 算法，还是可能被一些特殊数据卡成内存超限，这就需要采用可持久化左偏树进行优化。可持久化左偏树相较于左偏树，更适应于合并两个堆后还要保留原堆的情形。

首先建反图，从终点跑一遍最短路，求出每个可达的点到终点的最短路 d d d ，然后找出从终点出发的最短路径生成树。

对于原图上的某一个点 x x x ，如果该点到终点是可达的，那么遍历从该点出发经过每一条非树边到达的到终点可达的点 y y y ，会有 Δ e = e x , y + d y − d x Delta e=e_{x,y}+d_y-d_x Δe=ex,y​+dy​−dx​ 即相比于从点 x x x 出发到达终点的最短路径，从 x x x 出发经过点 y y y 到达终点的最短路径长 Δ e Delta e Δe。将点 x x x 的所有 Δ e Delta e Δe 和 y y y 存放在点 x x x 对应的堆中。最后，将最短路径生成树中的每个点按深度有小到大顺序一次将每个点的父节点的堆中的元素合并到该节点中。

这样，对于点 x x x 的堆中的堆顶元素，表示从点 x x x 出发经一条与之相连的非树边后到达终点的最短路径。

从起点开始每次选进行类似 Dijkstra 算法的操作，建一个优先队列，初始状态将起点 S S S 对应的左偏树堆顶的位置 r t [ S ] rt[S] rt[S] 和 次短路长度 d S + Δ e d_S+Delta e dS​+Δe 放到优先队列中。每次取优先队列中最短的路径，然后对于该路径，找到可能的次短路径放到优先队列中。可能的次短路径为当前的取出的元素对应于左偏树节点 y y y 的两个子节点，即从当前节点 x x x 出发经非树边到达终点的所有最短路径中比经非树边到达 y y y 对应在原图上的节点后到达终点的路径长的最短的两个路径，或者是 y y y 的堆顶的元素，即 y y y 对应在原图的点经与之相连的一条非树边后到达终点的最短的路径。

这样相较于未优化的 A ∗ A^* A∗ 算法，本质上是对每个节点上又加了一个优先队列，这样可以只把比当前路径短的所有可能的次短路径加入优先队列，而不是将所有可能结果加入优先队列，大大的优化了时间和空间复杂度。

#include<bits/stdc++.h>using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 5e3 + 10, M = 2e5 + 10;struct Leftist_Tree {int tot, rt[N];struct node {int dis, lc, rc, x;double val;} t[N * 200];Leftist_Tree() { t[0].dis = -1; }inline int merge(int x, int y) {if (!x || !y)return x | y;if (t[x].val > t[y].val)swap(x, y);int p = ++tot;t[p] = t[x], t[p].rc = merge(t[x].rc, y);if (t[t[p].lc].dis < t[t[p].rc].dis)swap(t[p].lc, t[p].rc);t[p].dis = t[t[p].rc].dis + 1;return p;}inline void insert(int &p, int x, double v) {++tot, t[tot] = {0, 0, 0, x, v};p = merge(p, tot);}
} L;struct Kth_Path {int n, m;int head[N], ver[M], Next[M], tot;int rh[N], rv[M], rn[M], rt;int fa[N];bool v[N], vis[N], ot[M];double edge[M], re[M], d[N], E;inline void add(int x, int y, double z) {ver[++tot] = y;edge[tot] = z;Next[tot] = head[x];head[x] = tot;}inline void add_r(int x, int y, double z) {rv[++rt] = y;re[rt] = z;rn[rt] = rh[x];rh[x] = rt;}struct node {int x;double v;inline bool operator<(node a) const {return v > a.v;}};inline void dijkstra() {for (int i = 1; i <= n; i++)d[i] = 1e18;memset(vis, false, sizeof(bool) * (n + 1));priority_queue<node> q;d[n] = 0;q.push({n, 0});while (!q.empty()) {int x = q.top().x;q.pop();if (vis[x])continue;vis[x] = true;for (int i = rh[x]; i; i = rn[i]) {int y = rv[i];double z = re[i];if (d[y] > d[x] + z)d[y] = d[x] + z, q.push({y, d[y]});}}}inline void init() {tot = rt = 0;memset(head, 0, sizeof(int) * (n + 1));memset(rh, 0, sizeof(int) * (n + 1));}inline void bfs1() {queue<int> q;memset(ot, false, sizeof(bool) * (m + 1));memset(v, false, sizeof(bool) * (n + 1));v[n] = true, q.push(n);while (!q.empty()) {int x = q.front();q.pop();for (int i = rh[x]; i; i = rn[i]) {int y = rv[i];double z = re[i];if (v[y] || d[y] != d[x] + z)continue;fa[y] = x, v[y] = ot[i] = true, q.push(y);}}}inline void bfs2() {queue<int> q;memset(v, false, sizeof(bool) * (n + 1));v[n] = true, q.push(n);while (!q.empty()) {int x = q.front();q.pop();if (fa[x])L.rt[x] = L.[x], L.rt[fa[x]]);for (int i = rh[x]; i; i = rn[i])if (ot[i] && !v[rv[i]])v[rv[i]] = true, q.push(rv[i]);}}inline int solve() {n = qr(), m = qr(), init();scanf("%lf", &E);for (int i = 1; i <= m; i++) {int x = qr(), y = qr();double z;scanf("%lf", &z);add(x, y, z), add_r(y, x, z);}dijkstra();if (E < d[1] * 2)return 1;bfs1();for (int x = 1; x <= n; x++) {if (!vis[x])continue;for (int i = head[x]; i; i = Next[i])if (!ot[i] && vis[ver[i]])L.[x], ver[i], d[ver[i]] + edge[i] - d[x]);}bfs2();E -= d[1];if (!L.rt[1] || E < d[1] + L.[1]].val)return 1;priority_queue<node> q;q.push({L.rt[1], d[1] + L.[1]].val});int cnt = 1;while (!q.empty()) {node t = q.top();q.pop();if (t.v > E)return cnt;E -= t.v, cnt++;if (L.t[t.x].lc && t.v - L.t[t.x].val + L.t[L.t[t.x].lc].val <= E)q.push({L.t[t.x].lc, t.v - L.t[t.x].val + L.t[L.t[t.x].lc].val});if (L.t[t.x].rc && t.v - L.t[t.x].val + L.t[L.t[t.x].rc].val <= E)q.push({L.t[t.x].rc, t.v - L.t[t.x].val + L.t[L.t[t.x].rc].val});if (L.rt[L.t[t.x].x] && t.v + L.[L.t[t.x].x]].val <= E)q.push({L.rt[L.t[t.x].x], t.v + L.[L.t[t.x].x]].val});}return cnt;}
} K;int main() {printf("%dn", K.solve());return 0;
}