This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: ERROR 1e-4
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1069
#include "../../template/template.hpp"
#include "../../graph/graph-template.hpp"
#include "../../graph/shortest-path/k-shortest-path.hpp"
int main() {
int N, M, K;
cin >> N >> M >> K;
int X, Y;
cin >> X >> Y;
--X, --Y;
vector< int > P(N), Q(N);
for(int i = 0; i < N; i++) {
cin >> P[i] >> Q[i];
}
Graph< double > g(N);
vector< int > x(M * 2), y(M * 2);
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
--a, --b;
g.add_directed_edge(a, b, hypot(P[a] - P[b], Q[a] - Q[b]));
x[i] = a, y[i] = b;
}
for(int i = 0; i < M; i++) {
int a = x[i], b = y[i];
x[i + M] = b, y[i + M] = a;
g.add_directed_edge(b, a, hypot(P[a] - P[b], Q[a] - Q[b]));
}
auto ans = k_shortest_path(g, X, Y, K);
for(int i = 0; i < K; i++) {
if(i < ans.size()) cout << ans[i].first << "\n";
else cout << -1 << "\n";
}
}
#line 1 "test/verify/yukicoder-1069.test.cpp"
// competitive-verifier: ERROR 1e-4
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1069
#line 1 "template/template.hpp"
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
os << p.first << " " << p.second;
return os;
}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
is >> p.first >> p.second;
return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
for(int i = 0; i < (int) v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
for(T &in : v) is >> in;
return is;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T = int64 >
vector< T > make_v(size_t a) {
return vector< T >(a);
}
template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}
template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
t = v;
}
template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
template< typename F >
struct FixPoint : F {
explicit FixPoint(F &&f) : F(forward< F >(f)) {}
template< typename... Args >
decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, forward< Args >(args)...);
}
};
template< typename F >
inline decltype(auto) MFP(F &&f) {
return FixPoint< F >{forward< F >(f)};
}
#line 5 "test/verify/yukicoder-1069.test.cpp"
#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 2 "graph/shortest-path/k-shortest-path.hpp"
#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;
}
#line 8 "test/verify/yukicoder-1069.test.cpp"
int main() {
int N, M, K;
cin >> N >> M >> K;
int X, Y;
cin >> X >> Y;
--X, --Y;
vector< int > P(N), Q(N);
for(int i = 0; i < N; i++) {
cin >> P[i] >> Q[i];
}
Graph< double > g(N);
vector< int > x(M * 2), y(M * 2);
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
--a, --b;
g.add_directed_edge(a, b, hypot(P[a] - P[b], Q[a] - Q[b]));
x[i] = a, y[i] = b;
}
for(int i = 0; i < M; i++) {
int a = x[i], b = y[i];
x[i + M] = b, y[i + M] = a;
g.add_directed_edge(b, a, hypot(P[a] - P[b], Q[a] - Q[b]));
}
auto ans = k_shortest_path(g, X, Y, K);
for(int i = 0; i < K; i++) {
if(i < ans.size()) cout << ans[i].first << "\n";
else cout << -1 << "\n";
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 01_sample_01.txt | AC | 6 ms | 4 MB |
g++ | 01_sample_02.txt | AC | 6 ms | 4 MB |
g++ | 01_sample_03.txt | AC | 6 ms | 4 MB |
g++ | 01_sample_04.txt | AC | 6 ms | 4 MB |
g++ | 98_challenge01.txt | AC | 54 ms | 7 MB |
g++ | 98_challenge02.txt | AC | 51 ms | 11 MB |
g++ | arand_halfsame.txt | AC | 8 ms | 4 MB |
g++ | arand_same.txt | AC | 9 ms | 4 MB |
g++ | arnd1.txt | AC | 7 ms | 4 MB |
g++ | arnd2.txt | AC | 8 ms | 4 MB |
g++ | arnd3.txt | AC | 7 ms | 4 MB |
g++ | arnd4.txt | AC | 6 ms | 4 MB |
g++ | arnd5.txt | AC | 7 ms | 4 MB |
g++ | brand_halfsame.txt | AC | 8 ms | 4 MB |
g++ | brand_same.txt | AC | 7 ms | 4 MB |
g++ | brnd1.txt | AC | 7 ms | 4 MB |
g++ | brnd2.txt | AC | 7 ms | 4 MB |
g++ | brnd3.txt | AC | 6 ms | 4 MB |
g++ | brnd4.txt | AC | 7 ms | 4 MB |
g++ | brnd5.txt | AC | 9 ms | 4 MB |
g++ | complete1.txt | AC | 6 ms | 4 MB |
g++ | complete_halfsame.txt | AC | 7 ms | 4 MB |
g++ | complete_same.txt | AC | 6 ms | 4 MB |
g++ | comptele21.txt | AC | 9 ms | 4 MB |
g++ | corner1.txt | AC | 8 ms | 4 MB |
g++ | corner2.txt | AC | 9 ms | 4 MB |
g++ | corner21.txt | AC | 8 ms | 4 MB |
g++ | corner22.txt | AC | 8 ms | 4 MB |
g++ | corner23.txt | AC | 8 ms | 4 MB |
g++ | easy_to_hard_rnd_mini3.txt | AC | 7 ms | 4 MB |
g++ | easy_to_hard_rnd_mini5.txt | AC | 6 ms | 4 MB |
g++ | hack | AC | 6 ms | 4 MB |
g++ | hack2 | AC | 6 ms | 4 MB |
g++ | hack3 | AC | 6 ms | 4 MB |
g++ | hand1.txt | AC | 6 ms | 4 MB |
g++ | hand2.txt | AC | 6 ms | 4 MB |
g++ | hand3.txt | AC | 6 ms | 4 MB |
g++ | mini1.txt | AC | 6 ms | 4 MB |
g++ | mini2.txt | AC | 6 ms | 4 MB |
g++ | mini3.txt | AC | 6 ms | 4 MB |
g++ | mini4.txt | AC | 6 ms | 4 MB |
g++ | mini5.txt | AC | 6 ms | 4 MB |
g++ | mini_halfsame.txt | AC | 6 ms | 4 MB |
g++ | mini_same.txt | AC | 6 ms | 4 MB |
g++ | mitsu1.txt | AC | 8 ms | 4 MB |
g++ | mitsu2.txt | AC | 7 ms | 4 MB |
g++ | mitsu3.txt | AC | 8 ms | 4 MB |
g++ | mitsu4.txt | AC | 8 ms | 4 MB |
g++ | mitsu5.txt | AC | 9 ms | 4 MB |
g++ | newrnd1.txt | AC | 7 ms | 4 MB |
g++ | newrnd2.txt | AC | 6 ms | 4 MB |
g++ | newrnd3.txt | AC | 8 ms | 4 MB |
g++ | newrnd4.txt | AC | 6 ms | 4 MB |
g++ | newrnd5.txt | AC | 8 ms | 4 MB |
g++ | rndmini1.txt | AC | 6 ms | 4 MB |
g++ | rndmini10.txt | AC | 6 ms | 4 MB |
g++ | rndmini11.txt | AC | 6 ms | 4 MB |
g++ | rndmini12.txt | AC | 6 ms | 4 MB |
g++ | rndmini13.txt | AC | 6 ms | 4 MB |
g++ | rndmini14.txt | AC | 6 ms | 4 MB |
g++ | rndmini15.txt | AC | 6 ms | 4 MB |
g++ | rndmini2.txt | AC | 6 ms | 4 MB |
g++ | rndmini3.txt | AC | 6 ms | 4 MB |
g++ | rndmini4.txt | AC | 6 ms | 4 MB |
g++ | rndmini5.txt | AC | 6 ms | 4 MB |
g++ | rndmini6.txt | AC | 6 ms | 4 MB |
g++ | rndmini7.txt | AC | 6 ms | 4 MB |
g++ | rndmini8.txt | AC | 6 ms | 4 MB |
g++ | rndmini9.txt | AC | 6 ms | 4 MB |
g++ | tree1.txt | AC | 7 ms | 4 MB |
g++ | tree2.txt | AC | 7 ms | 4 MB |
g++ | tree3.txt | AC | 7 ms | 4 MB |
g++ | tree4.txt | AC | 6 ms | 4 MB |
g++ | tree5.txt | AC | 6 ms | 4 MB |
g++ | tree_halfsame.txt | AC | 7 ms | 4 MB |
g++ | tree_same.txt | AC | 7 ms | 4 MB |
g++ | unique1.txt | AC | 8 ms | 4 MB |
g++ | unique2.txt | AC | 9 ms | 4 MB |
g++ | unique3.txt | AC | 6 ms | 4 MB |
g++ | unique4.txt | AC | 8 ms | 4 MB |
g++ | unique5.txt | AC | 8 ms | 4 MB |
g++ | uniquebig1.txt | AC | 7 ms | 4 MB |
g++ | uniquebig2.txt | AC | 7 ms | 4 MB |
clang++ | 01_sample_01.txt | AC | 6 ms | 4 MB |
clang++ | 01_sample_02.txt | AC | 6 ms | 4 MB |
clang++ | 01_sample_03.txt | AC | 6 ms | 4 MB |
clang++ | 01_sample_04.txt | AC | 6 ms | 4 MB |
clang++ | 98_challenge01.txt | AC | 53 ms | 7 MB |
clang++ | 98_challenge02.txt | AC | 50 ms | 11 MB |
clang++ | arand_halfsame.txt | AC | 8 ms | 4 MB |
clang++ | arand_same.txt | AC | 9 ms | 4 MB |
clang++ | arnd1.txt | AC | 7 ms | 4 MB |
clang++ | arnd2.txt | AC | 8 ms | 4 MB |
clang++ | arnd3.txt | AC | 7 ms | 4 MB |
clang++ | arnd4.txt | AC | 6 ms | 4 MB |
clang++ | arnd5.txt | AC | 7 ms | 4 MB |
clang++ | brand_halfsame.txt | AC | 7 ms | 4 MB |
clang++ | brand_same.txt | AC | 7 ms | 4 MB |
clang++ | brnd1.txt | AC | 7 ms | 4 MB |
clang++ | brnd2.txt | AC | 7 ms | 4 MB |
clang++ | brnd3.txt | AC | 7 ms | 4 MB |
clang++ | brnd4.txt | AC | 7 ms | 4 MB |
clang++ | brnd5.txt | AC | 9 ms | 4 MB |
clang++ | complete1.txt | AC | 6 ms | 4 MB |
clang++ | complete_halfsame.txt | AC | 7 ms | 4 MB |
clang++ | complete_same.txt | AC | 7 ms | 4 MB |
clang++ | comptele21.txt | AC | 9 ms | 4 MB |
clang++ | corner1.txt | AC | 8 ms | 4 MB |
clang++ | corner2.txt | AC | 9 ms | 4 MB |
clang++ | corner21.txt | AC | 8 ms | 4 MB |
clang++ | corner22.txt | AC | 8 ms | 4 MB |
clang++ | corner23.txt | AC | 8 ms | 4 MB |
clang++ | easy_to_hard_rnd_mini3.txt | AC | 6 ms | 4 MB |
clang++ | easy_to_hard_rnd_mini5.txt | AC | 6 ms | 4 MB |
clang++ | hack | AC | 6 ms | 4 MB |
clang++ | hack2 | AC | 6 ms | 4 MB |
clang++ | hack3 | AC | 6 ms | 4 MB |
clang++ | hand1.txt | AC | 6 ms | 4 MB |
clang++ | hand2.txt | AC | 6 ms | 4 MB |
clang++ | hand3.txt | AC | 6 ms | 4 MB |
clang++ | mini1.txt | AC | 6 ms | 4 MB |
clang++ | mini2.txt | AC | 7 ms | 4 MB |
clang++ | mini3.txt | AC | 6 ms | 4 MB |
clang++ | mini4.txt | AC | 6 ms | 4 MB |
clang++ | mini5.txt | AC | 7 ms | 4 MB |
clang++ | mini_halfsame.txt | AC | 7 ms | 4 MB |
clang++ | mini_same.txt | AC | 6 ms | 4 MB |
clang++ | mitsu1.txt | AC | 8 ms | 4 MB |
clang++ | mitsu2.txt | AC | 7 ms | 4 MB |
clang++ | mitsu3.txt | AC | 8 ms | 4 MB |
clang++ | mitsu4.txt | AC | 8 ms | 4 MB |
clang++ | mitsu5.txt | AC | 8 ms | 4 MB |
clang++ | newrnd1.txt | AC | 7 ms | 4 MB |
clang++ | newrnd2.txt | AC | 6 ms | 4 MB |
clang++ | newrnd3.txt | AC | 8 ms | 4 MB |
clang++ | newrnd4.txt | AC | 7 ms | 4 MB |
clang++ | newrnd5.txt | AC | 8 ms | 4 MB |
clang++ | rndmini1.txt | AC | 6 ms | 4 MB |
clang++ | rndmini10.txt | AC | 6 ms | 4 MB |
clang++ | rndmini11.txt | AC | 6 ms | 4 MB |
clang++ | rndmini12.txt | AC | 6 ms | 4 MB |
clang++ | rndmini13.txt | AC | 6 ms | 4 MB |
clang++ | rndmini14.txt | AC | 6 ms | 4 MB |
clang++ | rndmini15.txt | AC | 6 ms | 4 MB |
clang++ | rndmini2.txt | AC | 6 ms | 4 MB |
clang++ | rndmini3.txt | AC | 6 ms | 4 MB |
clang++ | rndmini4.txt | AC | 6 ms | 4 MB |
clang++ | rndmini5.txt | AC | 6 ms | 4 MB |
clang++ | rndmini6.txt | AC | 6 ms | 4 MB |
clang++ | rndmini7.txt | AC | 6 ms | 4 MB |
clang++ | rndmini8.txt | AC | 6 ms | 4 MB |
clang++ | rndmini9.txt | AC | 6 ms | 4 MB |
clang++ | tree1.txt | AC | 7 ms | 4 MB |
clang++ | tree2.txt | AC | 7 ms | 4 MB |
clang++ | tree3.txt | AC | 7 ms | 4 MB |
clang++ | tree4.txt | AC | 6 ms | 4 MB |
clang++ | tree5.txt | AC | 6 ms | 4 MB |
clang++ | tree_halfsame.txt | AC | 7 ms | 4 MB |
clang++ | tree_same.txt | AC | 7 ms | 4 MB |
clang++ | unique1.txt | AC | 8 ms | 4 MB |
clang++ | unique2.txt | AC | 9 ms | 4 MB |
clang++ | unique3.txt | AC | 6 ms | 4 MB |
clang++ | unique4.txt | AC | 7 ms | 4 MB |
clang++ | unique5.txt | AC | 8 ms | 4 MB |
clang++ | uniquebig1.txt | AC | 7 ms | 4 MB |
clang++ | uniquebig2.txt | AC | 7 ms | 4 MB |