K短路板子，在两个地方WA都是开小了空间...
求出 $T$ 到其他所有点的最短路树，记 $d[i]$ 为 $i$ 到 $T$ 的最短路。给每一个点分配一个前趋，如果多个相同则选其中一个。（注意有重边时要记录边而不是记录前趋的点！！！）
走 $S$ 到 $T$ 上的树边即为最短路，走一条非树边 $(u, v, c)$ 则会使费用增大 $d[v] + c - d[u]$。记该花费为非树边的费用，显然树边的费用为 $0$。
将一条从 $S$ 到 $T$ 的路径记为其经过的非树边序列 $p$，那么这条路径的权值和即为 $d[s] + \sum_{(u,v,c) \in p} (d[v] + c - d[u])$
求 $k$ 短路即求第 $k$ 小的合法非树边序列费用之和。
合法的非树边序列为相邻两条非树边 $e$，$f$，$e$ 在 $f$ 之前，$head(f)$ 需为 $tail(e)$ 在 $T$ 上的祖先或相同。
用一个堆来存储搜索的状态，当前的非树边权值和为优先级，再存储最后一条非树边的起点。
往后可以有两个决策，一为直接加上最后一条非树边的终点之后的非树边中，权值最小的那个。
二为将最后一条非树边替换为 $u$ 之后的非树边下一条比这条非树边大的。
发现需要用另一个堆维护每个点往后所有的非树边。发现 $u$ 和 $pre[u]$ 大部分非树边相同，只是多了一些以自身为起点的非树边，那么可以可持久化地添加非树边。
可以用可持久化左偏树，虽然论文里说的是它不可完全可持久化。
还是挺好写的，就是在合并的过程中用新的节点来合并。像线段树合并。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <functional> #include <queue> #define pii pair<int, int> #define fi first #define se second inline bool chkmin(int &a, const int &b) { return a > b ? a = b, 1 : 0; } inline bool chkmax(int &a, const int &b) { return a < b ? a = b, 1 : 0; } const int N = 8e3 + 7; const int INF = 0x3f3f3f3f; namespace Heap { struct Node { int lp, rp, v, dis, val; } tree[N * 100]; int root[N], tol; int newnode(int x = 0, int y = 0) { int p = ++tol; tree[p].lp = tree[p].rp = tree[p].dis = 0; tree[p].val = x; tree[p].v = y; return p; } inline void init() { tol = 0; tree[0].dis = -1; } int merge(int u, int v) { if (!u || !v) return u | v; if (tree[u].val > tree[v].val) std::swap(u, v); int p = newnode(); tree[p] = tree[u]; tree[p].rp = merge(tree[p].rp, v); if (tree[tree[p].lp].dis < tree[tree[p].rp].dis) std::swap(tree[p].lp, tree[p].rp); tree[p].dis = tree[tree[p].rp].dis + 1; return p; } } using namespace Heap; bool vis[N], done[N]; int d[N], pre[N], head1[N], head2[N], cnt; struct E { int v, ne, c; } e[200050]; void add(int u, int v, int c) { e[cnt].v = v; e[cnt].ne = head1[u]; e[cnt].c = c; head1[u] = cnt++; e[cnt].v = u; e[cnt].ne = head2[v]; e[cnt].c = c; head2[v] = cnt++; } void dijkstra(int s, int *head) { std::priority_queue<std::pii, std::vector<std::pii>, std::greater<std::pii> > que; que.push(std::pii(d[s] = 0, s)); while (!que.empty()) { std::pii p = que.top(); que.pop(); int u = p.se; if (done[u]) continue; done[u] = 1; for (int i = head[u]; ~i; i = e[i].ne) { int v = e[i].v, c = e[i].c; if (chkmin(d[v], d[u] + c)) { pre[v] = i; que.push(std::pii(d[v], v)); } } } } void dfs(int u) { if (vis[u]) return; vis[u] = 1; for (int i = head1[u]; ~i; i = e[i].ne) { int v = e[i].v, c = e[i].c; if (d[v] == INF || (i ^ 1) == pre[u]) continue; root[u] = merge(root[u], newnode(d[v] + c - d[u], v)); } if (~pre[u]) root[u] = merge(root[u], root[e[pre[u] ^ 1].v]); for (int i = head2[u]; ~i; i = e[i].ne) { if (pre[e[i].v] == i) dfs(e[i].v); } } int solve() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { vis[i] = root[i] = done[i] = 0; head1[i] = head2[i] = pre[i] = -1; d[i] = INF; } for (int i = 1, u, v, c; i <= m; i++) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } int s, t, k; scanf("%d%d%d", &s, &t, &k); dijkstra(t, head2); if (s == t) k++; if (k == 1) return d[s] == INF ? -1 : d[s]; init(); dfs(t); std::priority_queue< std::pii, std::vector<std::pii>, std::greater<std::pii> > que; if (root[s]) que.push(std::pii(d[s] + tree[root[s]].val, root[s])); for (k -= 2; k; k--) { if (que.empty()) return -1; std::pii p = que.top(); que.pop(); int i = p.se, j = root[tree[i].v]; if (j) que.push(std::pii(p.fi + tree[j].val, j)); if (tree[i].lp) que.push(std::pii(p.fi - tree[i].val + tree[tree[i].lp].val, tree[i].lp)); if (tree[i].rp) que.push(std::pii(p.fi - tree[i].val + tree[tree[i].rp].val, tree[i].rp)); } return que.empty() ? -1 : que.top().fi; } int main() { freopen("in.txt", "r", stdin); printf("%d\n", solve()); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11762494.html
