问题

对于带权有向图，定义路径的长度为经过的边的权值之和。两条路径不同当且仅当经过边的顺序不同。给一个带权有向图 G G G 以及起点和终点 s , t s,t s,t，求 G G G 中 s s s 到 t t t 权值前 k k k 小的路径。

朴素做法

问题转化

定义 d i s x dis_x disx​ 表示从 x x x 到 t t t 的最短路长度，权值为 w w w 的边 e : u → v e:u\to v e:u→v 的花费 δ ( e ) = d i s v − d i s u + w \delta(e)=dis_v-dis_u+w δ(e)=disv​−disu​+w

可以理解成若从 u u u 走向 t t t 时，沿着边 e e e 而不是最短路径上的边走，至少需要多走 δ ( e ) \delta(e) δ(e) 的距离。

先求出 G G G 中从 t t t 出发沿着反向边走的最短路树，那么一条从 s s s 到 t t t 的路径 P P P 是由若干条树边和非树边组成。 P P P 的长度可以表示为 l e n ( p ) = d i s s + ∑ e ∈ P δ ( e ) len(p)=dis_s+\sum_{e\in P}\delta(e) len(p)=diss​+e∈P∑​δ(e)

显然树边 e T e_T eT​ 满足 δ ( e T ) = 0 \delta(e_T)=0 δ(eT​)=0。若令 P ′ P' P′ 为 P P P 中的非树边构成的列表，则 l e n ( P ) = d i s s + ∑ e ′ ∈ P ′ δ ( e ′ ) len(P)=dis_s+\sum_{e'\in P'}\delta(e') len(P)=diss​+e′∈P′∑​δ(e′)

满足以下条件的所有列表 P ′ P' P′，与所有从 s s s 到 t t t 的路径 P P P 构成一一对应关系：

• P ′ P' P′ 中相邻的两条边 a → b , c → d a\to b,c\to d a→b,c→d，满足 b = c b=c b=c 或者 c c c 是 b b b 的祖先。

那么求长度前 k k k 小的路径 P P P，等价于求边权和前 k k k 小的合法列表 P ′ P' P′。

求解

令 E ( x ) E(x) E(x) 表示 x x x 以及所有 x x x 的祖先的出边中的非树边构成的集合，考虑以下算法：

• 用堆来维护合法的列表 P ′ P' P′。一开始堆中唯一的 P ′ P' P′ 为空。
• 每次取出边权和最小的 P ′ P' P′，设 P ′ P' P′ 中的最后一条边为 u → v u\to v u→v。
• 对于 E ( v ) E(v) E(v) 中的每一条边 e e e，将 P ′ ∪ e P'\cup e P′∪e 加入堆中。

这样可以保证每一个合法的 P ′ P' P′ 都恰好被生成一次。显然这是个正确的算法，但最坏情况下需要把所有合法的 P ′ P' P′ 都生成出来，这是无法接受的。

如果每次只取出 E ( v ) E(v) E(v) 中 δ ( e ) \delta(e) δ(e) 最小的一条边，并在更新堆的步骤中加入替换操作：

• 设 P ′ P' P′ 中的最后一条边为 e e e，倒数第二条边为 u → v u\to v u→v，将 e e e 替换成 E ( v ) E(v) E(v) 中的下一条边（假设 E ( v ) E(v) E(v) 中的边按 δ ( e ) \delta(e) δ(e) 从小到大排序）。

则每一个合法的 P ′ P' P′ 同样都是恰好被生成一次，且每取出一个 P ′ P' P′，只会新生成 O ( 1 ) O(1) O(1) 个新的 P ′ P' P′。

可持久化可并堆优化

在上述做法中，如果用可持久化可并堆来维护 E ( v ) E(v) E(v)，则建堆的总复杂度为 O ( m log ⁡ m ) O(m\log m) O(mlogm)。求解前 k k k 小的 P ′ P' P′ 的时间复杂度为 O ( k log ⁡ k ) O(k\log k) O(klogk)。那么总的复杂度为 O ( m log ⁡ m + k log ⁡ k ) O(m\log m+k\log k) O(mlogm+klogk)。

在实现的时候有一些小技巧：在堆中对每个 P ′ P' P′ 维护一个二元组。第一维表示 P ′ P' P′ 中的 δ ( e ) \delta(e) δ(e) 之和，第二维表示 P ′ P' P′ 中的最后一条边在可并堆中对应的节点编号。在替换操作中，将第二维分别换成原来节点的两个儿子，并修改第一维的值。加入操作中，设 P ′ P' P′ 中最后一条边为 u → v u\to v u→v，将第二维换成 E ( v ) E(v) E(v) 的根节点，并修改第一维的值。那么每次堆中最多新增三个元素。

例题

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

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

typedef pair<double, int> pi;

const int N = 5005;
const int M = 200005;
const double eps = 1e-8;
const double inf = 1e15;

int n, m, sz, cnt, last[N], rev_last[N], rt[N], fa[N];
double W, dis[N];
bool vis[N];
vector<int> dfn;
struct edge{int from, to, next; double w; bool is_tree_edge;}e[M * 2];
struct tree{int l, r, h, val; double key;}t[M * 10];

void addedge(int u, int v, double w)
{
	e[++cnt].from = u; e[cnt].to = v; e[cnt].w = w; e[cnt].next = last[u]; last[u] = cnt;
	e[++cnt].from = v; e[cnt].to = u; e[cnt].w = w; e[cnt].next = rev_last[v]; rev_last[v] = cnt;
}

int newnode(double key, int val)
{
	sz++; t[sz].key = key; t[sz].val = val; t[sz].h = 1;
	return sz;
}

int merge(int x, int y)
{
	if (!x || !y) return x + y;
	if (t[x].key > t[y].key) swap(x, y);
	int z = ++sz; t[z] = t[x];
	t[z].r = merge(t[z].r, y);
	if (t[t[z].l].h < t[t[z].r].h) swap(t[z].l, t[z].r);
	t[z].h = t[t[z].r].h + 1;
	return z;
}

void dijkstra()
{
	priority_queue<pi, vector<pi>, greater<pi> > que;
	for (int i = 1; i <= n; i++) dis[i] = inf;
	dis[n] = 0; que.push(make_pair(0, n));
	while (!que.empty())
	{
		int x = que.top().second; que.pop();
		while (!que.empty() && vis[x]) x = que.top().second, que.pop();
		if (vis[x]) break;
		vis[x] = 1;
		for (int i = rev_last[x]; i; i = e[i].next)
			if (dis[x] + e[i].w < dis[e[i].to])
			{
				dis[e[i].to] = dis[x] + e[i].w;
				que.push(make_pair(dis[e[i].to], e[i].to));
			}
	}
}

void build_SPT(int x)
{
	vis[x] = 1; dfn.push_back(x);
	for (int i = rev_last[x]; i; i = e[i].next)
		if (!vis[e[i].to] && fabs(dis[x] + e[i].w - dis[e[i].to]) < eps)
		{
			fa[e[i].to] = x;
			build_SPT(e[i].to);
			e[i].is_tree_edge = e[i ^ 1].is_tree_edge = 1;
		}
}

void build_heap()
{
	for (int i = 2; i <= cnt; i += 2)
	{
		int x = e[i].from, y = e[i].to;
		if (!e[i].is_tree_edge && vis[x] && vis[y])
			rt[x] = merge(rt[x], newnode(dis[y] - dis[x] + e[i].w, y));
	}
	for (int i = 1; i < dfn.size(); i++)
		rt[dfn[i]] = merge(rt[dfn[i]], rt[fa[dfn[i]]]);
}

int solve()
{
	priority_queue<pi, vector<pi>, greater<pi> > que;
	int ans = 0;
	if (dis[1] < W + eps) W -= dis[1], ans++;
	if (rt[1]) que.push(make_pair(t[rt[1]].key, rt[1]));
	while (!que.empty())
	{
		double w = que.top().first; int x = que.top().second; que.pop();
		if (w + dis[1] > W) break;
		W -= w + dis[1]; ans++;
		if (t[x].l) que.push(make_pair(t[t[x].l].key + w - t[x].key, t[x].l));
		if (t[x].r) que.push(make_pair(t[t[x].r].key + w - t[x].key, t[x].r));
		if (rt[t[x].val]) que.push(make_pair(t[rt[t[x].val]].key + w, rt[t[x].val]));
	}
	return ans;
}

int main()
{
	scanf("%d%d%lf", &n, &m, &W);
	cnt = 1;
	for (int i = 1; i <= m; i++)
	{
		int x, y; double w; scanf("%d%d%lf", &x, &y, &w);
		if (x != n) addedge(x, y, w);
	}
	dijkstra();
	memset(vis, 0, sizeof(vis));
	build_SPT(n);
	build_heap();
	printf("%d\n", solve());
	return 0;
}