\(k\) 短路
这玩意据说可以用 A* 搞，或者用什么可持久化堆或者左偏树维护最短路树？
笔者不才，只好用分层图套 dijkstra 写一下。
思路来自这里。
大体流程：把一个点拆成 \(k\) 个（其实就是在 dis 数组加一维），对于一条边 \(<u,v>\)，可以从 \(u\) 的层数开始找能更新的 \(v\) 的第几层，然后挨个继承上一层，最后把 \(u\) 能更新的更新了。
核心代码：
for (int i = hd[u]; i; i = nt[i])
{
int v = ed[i];
int w = co[i] + d;
int p = -1;
for (int d = l; d < k; d++)
{
if (dis[v][d] > w)
{
p = d;
break;
}
// 如果是要求严格第 k 短，则需要加上下面这两句话：
else if (dis[v][k] == w)
break;
}
if (p != -1)
{
for (int d = k - 1; d > p; d--)
{
if (dis[v][d - 1] == 0x3f3f3f3f)
continue;
dis[v][d] = dis[v][d - 1];
pq.push ({dis[v][d], d, v});
}
dis[v][p] = w;
pq.push ({w, p, v});
}
}
例题：
bxgzoj 040306 内部 oj。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 810, M = 8010, K = 45;
int n, m, k, ans;
int hd[N], ed[M], nt[M], co[M], cnt;
int dis[N][K];
bool vis[N][K];
struct node
{
int d, l, u;
bool operator <(const node a) const
{
return (d == a.d ? l > a.l : d > a.d);
}
};
priority_queue<node> pq;
void add_edge (int u, int v, int w)
{
ed[++cnt] = v;
co[cnt] = w;
nt[cnt] = hd[u];
hd[u] = cnt;
}
void dijkstra()
{
memset (dis, 0x3f, sizeof dis);
dis[1][0] = 0;
pq.push ({0, 0, 1});
while (!pq.empty())
{
int u = pq.top().u;
int l = pq.top().l;
int d = pq.top().d;
pq.pop();
if (vis[u][l])
continue;
vis[u][l] = 1;
if (u == n)
continue;
for (int i = hd[u]; i; i = nt[i])
{
int v = ed[i];
int w = co[i] + d;
int p = -1;
for (int d = l; d < k; d++)
{
if (dis[v][d] > w)
{
p = d;
break;
}
}
if (p != -1)
{
for (int d = k - 1; d > p; d--)
{
if (dis[v][d - 1] == 0x3f3f3f3f)
continue;
dis[v][d] = dis[v][d - 1];
pq.push ({dis[v][d], d, v});
}
dis[v][p] = w;
pq.push ({w, p, v});
}
}
}
}
int main()
{
scanf ("%d%d%d", &k, &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf ("%d%d%d", &u, &v, &w);
add_edge (u, v, w);
add_edge (v, u, w);
}
dijkstra();
for (int i = 0; i < k; i++)
ans += dis[n][i];
printf ("%d\n", ans);
return 0;
}
洛谷 P2865 次短当成 \(k\) 短做。
洛谷 P2901 据说可以用拓扑搞。
POJ 2449 死因未知。