/
K_shortest_path.hpp
94 lines (87 loc) · 2.5 KB
/
K_shortest_path.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "graph/base.hpp"
// (cost, vs, es)
template <typename T, typename GT>
vc<tuple<T, vc<int>, vc<int>>> K_shortest_path(GT& G, int s, int t, int K) {
assert(GT::is_directed);
const int N = G.N;
// (cost, vs, es)
vc<tuple<T, vc<int>, vc<int>>> res;
// 探索の起点 (es, ng_edges)
vc<pair<vc<int>, vc<int>>> nodes;
// 答の候補 (cost, es, ng_es, n), (ng_es, n):その path を見つけたときの条件
vc<tuple<T, vc<int>, vc<int>, int>> paths;
nodes.eb(vc<int>(), vc<int>());
vc<T> dist(N, infty<T>);
vc<bool> ng_v(N);
vc<bool> ng_e(G.M);
vc<int> par(N, -1);
while (len(res) < K) {
for (auto&& [es, ng_es]: nodes) {
fill(all(par), -1);
fill(all(ng_v), 0);
fill(all(ng_e), 0);
fill(all(dist), infty<T>);
T pref_cost = 0;
for (auto&& x: es) pref_cost += G.edges[x].cost;
for (auto&& x: es) ng_v[G.edges[x].frm] = 1, ng_e[x] = 1;
for (auto&& x: ng_es) ng_e[x] = 1;
// dijkstra
pqg<pair<T, int>> que;
auto add = [&](int v, T d, int p) -> void {
if (chmin(dist[v], d)) {
que.emplace(d, v);
par[v] = p;
}
};
int s0 = (es.empty() ? s : G.edges[es.back()].to);
add(s0, pref_cost, -1);
while (len(que)) {
auto [dv, v] = POP(que);
if (dv != dist[v]) continue;
if (v == t) break;
for (auto&& e: G[v]) {
if (ng_e[e.id] || ng_v[e.to]) continue;
add(e.to, dv + e.cost, e.id);
}
}
// failed
if (par[t] == -1) continue;
// restore path
vc<int> add_e;
{
int v = t;
while (v != s0) {
add_e.eb(par[v]);
v = G.edges[par[v]].frm;
}
}
reverse(all(add_e));
int n = len(es);
// find a path
es.insert(es.end(), all(add_e));
paths.eb(dist[t], es, ng_es, n);
}
// choose best path
if (len(paths) == 0) break;
pair<int, T> best = {-1, infty<T>};
FOR(i, len(paths)) {
T cost = get<0>(paths[i]);
if (chmin(best.se, cost)) best.fi = i;
}
int idx = best.fi;
swap(paths[idx], paths[len(paths) - 1]);
auto [cost, es, ng_es, n] = POP(paths);
vc<int> vs = {s};
for (auto&& x: es) vs.eb(G.edges[x].to);
res.eb(cost, vs, es);
nodes.clear();
FOR(k, n, len(es)) {
// k 番目の辺までを固定して
vc<int> new_es = {es.begin(), es.begin() + k};
vc<int> new_ng = ng_es;
new_ng.eb(es[k]);
nodes.eb(new_es, new_ng);
}
}
return res;
}