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 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 | 55 ms | 7 MB |
g++ | 98_challenge02.txt | AC | 53 ms | 11 MB |
g++ | arand_halfsame.txt | AC | 9 ms | 4 MB |
g++ | arand_same.txt | AC | 9 ms | 4 MB |
g++ | arnd1.txt | AC | 8 ms | 4 MB |
g++ | arnd2.txt | AC | 9 ms | 4 MB |
g++ | arnd3.txt | AC | 8 ms | 4 MB |
g++ | arnd4.txt | AC | 7 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 | 7 ms | 4 MB |
g++ | brnd4.txt | AC | 7 ms | 4 MB |
g++ | brnd5.txt | AC | 9 ms | 4 MB |
g++ | complete1.txt | AC | 7 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 | 9 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 | 7 ms | 4 MB |
g++ | mini2.txt | AC | 7 ms | 4 MB |
g++ | mini3.txt | AC | 6 ms | 4 MB |
g++ | mini4.txt | AC | 7 ms | 4 MB |
g++ | mini5.txt | AC | 7 ms | 4 MB |
g++ | mini_halfsame.txt | AC | 7 ms | 4 MB |
g++ | mini_same.txt | AC | 7 ms | 4 MB |
g++ | mitsu1.txt | AC | 9 ms | 4 MB |
g++ | mitsu2.txt | AC | 8 ms | 4 MB |
g++ | mitsu3.txt | AC | 9 ms | 4 MB |
g++ | mitsu4.txt | AC | 8 ms | 4 MB |
g++ | mitsu5.txt | AC | 10 ms | 4 MB |
g++ | newrnd1.txt | AC | 9 ms | 4 MB |
g++ | newrnd2.txt | AC | 7 ms | 4 MB |
g++ | newrnd3.txt | AC | 9 ms | 4 MB |
g++ | newrnd4.txt | AC | 7 ms | 4 MB |
g++ | newrnd5.txt | AC | 9 ms | 4 MB |
g++ | rndmini1.txt | AC | 7 ms | 4 MB |
g++ | rndmini10.txt | AC | 7 ms | 4 MB |
g++ | rndmini11.txt | AC | 6 ms | 4 MB |
g++ | rndmini12.txt | AC | 7 ms | 4 MB |
g++ | rndmini13.txt | AC | 6 ms | 4 MB |
g++ | rndmini14.txt | AC | 6 ms | 4 MB |
g++ | rndmini15.txt | AC | 7 ms | 4 MB |
g++ | rndmini2.txt | AC | 7 ms | 4 MB |
g++ | rndmini3.txt | AC | 7 ms | 4 MB |
g++ | rndmini4.txt | AC | 7 ms | 4 MB |
g++ | rndmini5.txt | AC | 7 ms | 4 MB |
g++ | rndmini6.txt | AC | 7 ms | 4 MB |
g++ | rndmini7.txt | AC | 7 ms | 4 MB |
g++ | rndmini8.txt | AC | 7 ms | 4 MB |
g++ | rndmini9.txt | AC | 6 ms | 4 MB |
g++ | tree1.txt | AC | 8 ms | 4 MB |
g++ | tree2.txt | AC | 8 ms | 4 MB |
g++ | tree3.txt | AC | 8 ms | 4 MB |
g++ | tree4.txt | AC | 7 ms | 4 MB |
g++ | tree5.txt | AC | 7 ms | 4 MB |
g++ | tree_halfsame.txt | AC | 8 ms | 4 MB |
g++ | tree_same.txt | AC | 8 ms | 4 MB |
g++ | unique1.txt | AC | 8 ms | 4 MB |
g++ | unique2.txt | AC | 9 ms | 4 MB |
g++ | unique3.txt | AC | 7 ms | 4 MB |
g++ | unique4.txt | AC | 8 ms | 4 MB |
g++ | unique5.txt | AC | 9 ms | 4 MB |
g++ | uniquebig1.txt | AC | 8 ms | 4 MB |
g++ | uniquebig2.txt | AC | 8 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 | 9 ms | 4 MB |
clang++ | arand_same.txt | AC | 9 ms | 4 MB |
clang++ | arnd1.txt | AC | 8 ms | 4 MB |
clang++ | arnd2.txt | AC | 9 ms | 4 MB |
clang++ | arnd3.txt | AC | 8 ms | 4 MB |
clang++ | arnd4.txt | AC | 6 ms | 4 MB |
clang++ | arnd5.txt | AC | 7 ms | 4 MB |
clang++ | brand_halfsame.txt | AC | 8 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 | 7 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 | 7 ms | 4 MB |
clang++ | easy_to_hard_rnd_mini5.txt | AC | 7 ms | 4 MB |
clang++ | hack | AC | 7 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 | 7 ms | 4 MB |
clang++ | mini2.txt | AC | 7 ms | 4 MB |
clang++ | mini3.txt | AC | 7 ms | 4 MB |
clang++ | mini4.txt | AC | 7 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 | 9 ms | 4 MB |
clang++ | newrnd1.txt | AC | 8 ms | 4 MB |
clang++ | newrnd2.txt | AC | 7 ms | 4 MB |
clang++ | newrnd3.txt | AC | 8 ms | 4 MB |
clang++ | newrnd4.txt | AC | 7 ms | 4 MB |
clang++ | newrnd5.txt | AC | 9 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 | 8 ms | 4 MB |
clang++ | tree_same.txt | AC | 7 ms | 4 MB |
clang++ | unique1.txt | AC | 8 ms | 4 MB |
clang++ | unique2.txt | AC | 8 ms | 4 MB |
clang++ | unique3.txt | AC | 6 ms | 4 MB |
clang++ | unique4.txt | AC | 8 ms | 4 MB |
clang++ | unique5.txt | AC | 9 ms | 4 MB |
clang++ | uniquebig1.txt | AC | 7 ms | 4 MB |
clang++ | uniquebig2.txt | AC | 7 ms | 4 MB |