結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 MitI_7
|
| 提出日時 | 2022-01-25 18:58:08 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,856 bytes |
| コンパイル時間 | 2,571 ms |
| コンパイル使用メモリ | 168,976 KB |
| 実行使用メモリ | 10,752 KB |
| 最終ジャッジ日時 | 2024-05-09 19:55:27 |
| 合計ジャッジ時間 | 6,226 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,752 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
ソースコード
#include <iostream>
#include <array>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <string>
#include <climits>
#include <cassert>
#include <iomanip>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <fstream>
#include <random>
#include <functional>
#define LEN(x) (long long)(x.size())
#define FOR(i, a, n) for(int i=(a);i<(n); ++i)
#define FOE(i, a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_COUNT32(bit) (__builtin_popcount(bit))
#define BIT_COUNT64(bit) (__builtin_popcountll(bit))
typedef long long LL;
template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts> auto make_v(size_t a, Ts... ts){ return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));} // C++14
template<typename T,typename V> typename std::enable_if<std::is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename std::enable_if<std::is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
void print() { std::cout << std::endl; }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { std::cout << head; if (sizeof...(tail) != 0) {std::cout << " ";} print(std::forward<Tail>(tail)...); }
template <class T> void print(std::vector<T> &v) {for (auto& a : v) { std::cout << a; if (&a != &v.back()) {std::cout << " ";} }std::cout << std::endl;}
template <class T> void print(std::vector<std::vector<T>> &vv) { for (auto& v : vv) { print(v); }}
void debug() { std::cerr << std::endl; }
template <class Head, class... Tail> void debug(Head&& head, Tail&&... tail) { std::cerr << head; if (sizeof...(tail) != 0) {std::cerr << " ";} print(std::forward<Tail>(tail)...); }
template <class T> void debug(std::vector<T> &v) {for (auto& a : v) { std::cerr << a; if (&a != &v.back()) {std::cerr << " ";} }std::cerr << std::endl;}
template <class T> void debug(std::vector<std::vector<T>> &vv) { for (auto& v : vv) { print(v); }}
inline bool inside(long long y, long long x, long long H, long long W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline T manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }
bool is_bit_on(const unsigned long long bit, const unsigned int i) { return (bit >> i) & 1u; }
unsigned long long bit_set(const unsigned long long bit, const unsigned int i, const unsigned int b) {
assert(b == 0 or b == 1);
if (b == 0) { return bit & ~(1ull << i); }
else {return bit | (1ull << i); }
}
template<class T> inline std::vector<T> unique(std::vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v;
}
// 初項s交差d長さnの数列の和
long long sum_of_arithmetic_progression(long long s, long long d, long long n) {
return n * (2 * s + (n - 1) * d) / 2;
}
// xが2の階乗かどうか判定
bool is_power_of_two(long long x) {
return !(x & (x - 1));
}
long long gcd(long long a, long long b) {
if (b == 0) { return a; }
return gcd(b, a % b);
}
long long gcd(std::vector<long long> &v) {
long long ans = v[0];
for (int i = 1; i < (int) v.size(); ++i) {
ans = gcd(ans, v[i]);
}
return ans;
}
long long lcm(long long a, long long b) {
long long g = gcd(a, b);
return a / g * b;
}
const int INF = 1u << 30u; // 1,073,741,824
const long long LINF = 1ull << 60u;
const double EPS = 1e-9;
const long double PI = acos(-1.0);
const std::vector<int> dy2 = {0, 1}, dx2 = {1, 0}; // 右，下
const std::vector<int> dy4 = {0, 1, 0, -1}, dx4 = {1, 0, -1, 0};
const std::vector<int> dy6 = {0, -1, 0, 1, 1, 1}, dx6 = {1, 0, -1, 0, 1, -1};
const std::vector<int> dy8 = {0, -1, 0, 1, 1, -1, -1, 1}, dx8 = {1, 0, -1, 0, 1, 1, -1, -1};
using namespace std;
template<typename T> class Edge {
public:
const int no;
const int u;
const int v;
const T distance;
Edge(int no, int u, int v, T distance) : no(no), u(u), v(v), distance(distance) {
}
};
template<typename T> class KShortestPath {
public:
const int num_nodes;
const int K;
private:
vector<vector<int>> graph;
vector<Edge<T>> edges;
vector<T> distance;
vector<vector<int>> A;
std::priority_queue<pair<T, vector<int>>, std::vector<pair<T, vector<int>>>, std::greater<pair<T, vector<int>>>> B; // deviation path
vector<bool> removed_edge;
public:
KShortestPath(const int num_nodes, const int K) : num_nodes(num_nodes), K(K) {
this->graph.resize(num_nodes);
}
void add_directed_edge(const int u, const int v, const T w) {
const int no = this->edges.size();
this->edges.emplace_back(Edge(no, u, v, w));
this->graph[u].emplace_back(no);
}
Edge<T> get_edge(const int edge_no) const {
return this->edges[edge_no];
}
// 0-index
T k_shortest_path_distance(const int k) const {
assert(k < K);
return this->distance[k];
}
// 0-index
vector<int> k_shortest_path(const int k) const {
assert(k < K);
return this->A[k];
}
int num_shortest_path() const {
return A.size();
}
void build(const int s, const int t) {
assert(s < num_nodes);
assert(t < num_nodes);
this->removed_edge.resize(this->edges.size());
{
auto[dist, path] = this->dijkstra(s, t);
this->A.emplace_back(path);
this->distance.emplace_back(dist);
}
while (A.size() < this->K) {
const auto last_path = this->A.back();
vector<int> spur_root;
T now_distance = 0;
for (int i = 0; i < int(last_path.size()); ++i) {
int edge_idx = last_path[i];
const auto &edge = this->edges[edge_idx];
const int spur_node = edge.u;
// 使えないedgeを求める
vector<int> rem;
for (const auto &path_k : this->A) {
if (int(path_k.size()) > i) {
bool same = true;
for (int j = 0; j < spur_root.size(); ++j) {
same &= (path_k[j] == spur_root[j]);
}
if (same) {
this->removed_edge[path_k[i]] = true;
rem.emplace_back(path_k[i]);
}
}
}
auto [dist, suf_path] = this->dijkstra(spur_node, t);
for (auto a : rem) {
this->removed_edge[a] = false;
}
// spur_node -> t へのパスがみつからなかった
if (suf_path.empty()) {
spur_root.push_back(edge_idx);
now_distance += edge.distance;
continue;
}
vector<int> path = spur_root;
path.insert(path.end(), suf_path.begin(), suf_path.end());
this->B.push({now_distance + dist, path});
spur_root.push_back(edge_idx);
now_distance += edge.distance;
}
while (not B.empty()) {
if (A.back() != this->B.top().second) {
this->A.emplace_back(this->B.top().second);
this->distance.emplace_back(B.top().first);
B.pop();
break;
}
B.pop();
}
}
}
private:
// 負辺がないとき用
std::pair<T, std::vector<int>> dijkstra(const int start, const int end) const {
//[(最短距離, node番号)]のque(距離が近い順にとりだす)
std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> que;
que.push({0, start});
std::vector<pair<int, int>> prev(this->num_nodes); // 経路復元用
std::vector<T> distance(this->num_nodes, numeric_limits<T>::max() / 3); // startからの距離
std::vector<bool> used(this->num_nodes);
distance[start] = 0;
while (not que.empty()) {
const auto [now_dist, u] = que.top();
que.pop();
if (used[u]) {
continue;
}
used[u] = true;
for (const auto edge_idx : this->graph[u]) {
if (this->removed_edge[edge_idx]) {
continue;
}
const auto edge = this->edges[edge_idx];
const auto v = edge.v;
const auto new_dist = now_dist + edge.distance;
if (new_dist < distance[v]) {
prev[v] = {u, edge_idx};
distance[v] = new_dist;
que.push({new_dist, v});
}
}
}
// t にたどり着けなかった
if (not used[end]) {
return {-1, {}};
}
vector<int> path;
int now = end;
int edge_idx = 0;
while (now != start) {
path.emplace_back(prev[now].second);
now = prev[now].first;
}
reverse(path.begin(), path.end());
return {distance[end], path};
}
};
int main() {
int N, M, K, X, Y;
cin >> N >> M >> K;
cin >> X >> Y;
X--; Y--;
vector<int> P(N), Q(N);
for (int i = 0; i < N; ++i) {
cin >> P[i] >> Q[i];
}
KShortestPath<double> ksp(N, K);
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
a--; b--;
auto d = sqrt((P[a] - P[b]) * (P[a] - P[b]) + (Q[a] - Q[b]) * (Q[a] - Q[b]));
ksp.add_directed_edge(a, b, d);
ksp.add_directed_edge(b, a, d);
}
ksp.build(X, Y);
for (int i = 0; i < K; ++i) {
if (i < ksp.num_shortest_path()) {
cout << fixed << setprecision(10) << ksp.k_shortest_path_distance(i) << endl;
}
else {
cout << -1 << endl;
}
}
return 0;
}