This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/shortest-path/k-shortest-path.hpp"
頂点 $s$ から $t$ へのパス(Path) のうち, 昇順 $k$ 個のパスの長さを Yen’s Algorithm により求める.
パス(Path, 道) は同じ頂点を通らない経路である.
verify が甘いため合っているかかなり不安です
k_shotest_path(g, s, t, k)
: 重み付き有向グラフ g
の頂点 s
から t
へのパスのうち, 昇順 k
個のパスの長さとそのパスの辺番号の列を返す(パスの個数が k
個に満たないとき全てを返す).#pragma once
#include "../graph-template.hpp"
/**
* @brief K-Shortest-Path
*
* @see https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
*/
template <typename T>
vector<pair<T, vector<int> > > k_shortest_path(const Graph<T> &g, int s, int t,
int k) {
assert(s != t);
int N = (int)g.size();
int M = 0;
for (int i = 0; i < N; i++) M += (int)g[i].size();
vector<int> latte(M), malta(M);
vector<T> cost(M);
for (int i = 0; i < N; i++) {
for (auto &e : g[i]) {
latte[e.idx] = i;
malta[e.idx] = e.to;
cost[e.idx] = e.cost;
}
}
const auto INF = numeric_limits<T>::max();
vector<int> dame(M, -1);
int timestamp = 0;
auto shortest_path = [&](vector<T> &dist, vector<int> &from, vector<int> &id,
int st) {
using Pi = pair<T, int>;
priority_queue<Pi, vector<Pi>, greater<> > que;
que.emplace(dist[st], st);
while (!que.empty()) {
T cost;
int idx;
tie(cost, idx) = que.top();
que.pop();
if (dist[idx] < cost) continue;
if (idx == t) return;
for (auto &e : g[idx]) {
auto next_cost = cost + e.cost;
if (dist[e.to] <= next_cost) continue;
if (dame[e.idx] == timestamp) continue;
dist[e.to] = next_cost;
from[e.to] = idx;
id[e.to] = e.idx;
que.emplace(dist[e.to], e.to);
}
}
};
auto restore = [](const vector<int> &es, const vector<int> &vs, int from,
int to) {
vector<int> tap;
while (to != from) {
tap.emplace_back(es[to]);
to = vs[to];
}
reverse(begin(tap), end(tap));
return tap;
};
vector<T> dist(g.size(), INF);
vector<int> from(g.size(), -1), id(g.size(), -1);
dist[s] = 0;
shortest_path(dist, from, id, s);
if (dist[t] == INF) return {};
vector<pair<T, vector<int> > > A;
set<pair<T, vector<int> > > B;
A.emplace_back(dist[t], restore(id, from, s, t));
for (int i = 1; i < k; i++) {
dist.assign(g.size(), INF);
from.assign(g.size(), -1);
id.assign(g.size(), -1);
dist[s] = 0;
vector<int> candidate(A.size());
iota(begin(candidate), end(candidate), 0);
auto &last_path = A.back().second;
int cur = s;
for (int j = 0; j < last_path.size(); j++) {
for (auto &k : candidate) {
if (j < A[k].second.size()) dame[A[k].second[j]] = timestamp;
}
vector<T> dist2{dist};
vector<int> from2{from}, id2{id};
shortest_path(dist2, from2, id2, cur);
++timestamp;
if (dist2[t] != INF) {
auto path = restore(id2, from2, s, t);
bool ok = true;
for (auto &p : candidate) {
if (path == A[p].second) {
ok = false;
break;
}
}
if (ok) B.emplace(dist2[t], path);
}
vector<int> accept;
for (auto &k : candidate) {
if (j < A[k].second.size() && A[k].second[j] == last_path[j]) {
accept.emplace_back(k);
}
}
dist[malta[last_path[j]]] =
dist[latte[last_path[j]]] + cost[last_path[j]];
from[malta[last_path[j]]] = latte[last_path[j]];
id[malta[last_path[j]]] = last_path[j];
cur = malta[last_path[j]];
candidate = move(accept);
}
if (B.size()) {
A.emplace_back(*B.begin());
B.erase(B.begin());
}
}
return A;
}
#line 2 "graph/shortest-path/k-shortest-path.hpp"
#line 2 "graph/graph-template.hpp"
/**
* @brief Graph Template(グラフテンプレート)
*/
template <typename T = int>
struct Edge {
int from, to;
T cost;
int idx;
Edge() = default;
Edge(int from, int to, T cost = 1, int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
operator int() const { return to; }
};
template <typename T = int>
struct Graph {
vector<vector<Edge<T> > > g;
int es;
Graph() = default;
explicit Graph(int n) : g(n), es(0) {}
size_t size() const { return g.size(); }
void add_directed_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es++);
}
void add_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void read(int M, int padding = -1, bool weighted = false,
bool directed = false) {
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (directed)
add_directed_edge(a, b, c);
else
add_edge(a, b, c);
}
}
inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }
inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};
template <typename T = int>
using Edges = vector<Edge<T> >;
#line 4 "graph/shortest-path/k-shortest-path.hpp"
/**
* @brief K-Shortest-Path
*
* @see https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
*/
template <typename T>
vector<pair<T, vector<int> > > k_shortest_path(const Graph<T> &g, int s, int t,
int k) {
assert(s != t);
int N = (int)g.size();
int M = 0;
for (int i = 0; i < N; i++) M += (int)g[i].size();
vector<int> latte(M), malta(M);
vector<T> cost(M);
for (int i = 0; i < N; i++) {
for (auto &e : g[i]) {
latte[e.idx] = i;
malta[e.idx] = e.to;
cost[e.idx] = e.cost;
}
}
const auto INF = numeric_limits<T>::max();
vector<int> dame(M, -1);
int timestamp = 0;
auto shortest_path = [&](vector<T> &dist, vector<int> &from, vector<int> &id,
int st) {
using Pi = pair<T, int>;
priority_queue<Pi, vector<Pi>, greater<> > que;
que.emplace(dist[st], st);
while (!que.empty()) {
T cost;
int idx;
tie(cost, idx) = que.top();
que.pop();
if (dist[idx] < cost) continue;
if (idx == t) return;
for (auto &e : g[idx]) {
auto next_cost = cost + e.cost;
if (dist[e.to] <= next_cost) continue;
if (dame[e.idx] == timestamp) continue;
dist[e.to] = next_cost;
from[e.to] = idx;
id[e.to] = e.idx;
que.emplace(dist[e.to], e.to);
}
}
};
auto restore = [](const vector<int> &es, const vector<int> &vs, int from,
int to) {
vector<int> tap;
while (to != from) {
tap.emplace_back(es[to]);
to = vs[to];
}
reverse(begin(tap), end(tap));
return tap;
};
vector<T> dist(g.size(), INF);
vector<int> from(g.size(), -1), id(g.size(), -1);
dist[s] = 0;
shortest_path(dist, from, id, s);
if (dist[t] == INF) return {};
vector<pair<T, vector<int> > > A;
set<pair<T, vector<int> > > B;
A.emplace_back(dist[t], restore(id, from, s, t));
for (int i = 1; i < k; i++) {
dist.assign(g.size(), INF);
from.assign(g.size(), -1);
id.assign(g.size(), -1);
dist[s] = 0;
vector<int> candidate(A.size());
iota(begin(candidate), end(candidate), 0);
auto &last_path = A.back().second;
int cur = s;
for (int j = 0; j < last_path.size(); j++) {
for (auto &k : candidate) {
if (j < A[k].second.size()) dame[A[k].second[j]] = timestamp;
}
vector<T> dist2{dist};
vector<int> from2{from}, id2{id};
shortest_path(dist2, from2, id2, cur);
++timestamp;
if (dist2[t] != INF) {
auto path = restore(id2, from2, s, t);
bool ok = true;
for (auto &p : candidate) {
if (path == A[p].second) {
ok = false;
break;
}
}
if (ok) B.emplace(dist2[t], path);
}
vector<int> accept;
for (auto &k : candidate) {
if (j < A[k].second.size() && A[k].second[j] == last_path[j]) {
accept.emplace_back(k);
}
}
dist[malta[last_path[j]]] =
dist[latte[last_path[j]]] + cost[last_path[j]];
from[malta[last_path[j]]] = latte[last_path[j]];
id[malta[last_path[j]]] = last_path[j];
cur = malta[last_path[j]];
candidate = move(accept);
}
if (B.size()) {
A.emplace_back(*B.begin());
B.erase(B.begin());
}
}
return A;
}