This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#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
#pragma once #include "../graph-template.hpp" /** * @brief K-Shortest-Path * @docs docs/k-shortest-path.md * @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 * @docs docs/k-shortest-path.md * @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; }