結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー | MitI_7 |
提出日時 | 2022-01-26 00:20:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 11,673 bytes |
コンパイル時間 | 2,556 ms |
コンパイル使用メモリ | 174,552 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-23 15:09:32 |
合計ジャッジ時間 | 5,592 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 366 ms
6,940 KB |
testcase_05 | AC | 436 ms
11,776 KB |
testcase_06 | AC | 8 ms
6,944 KB |
testcase_07 | AC | 10 ms
6,944 KB |
testcase_08 | AC | 8 ms
6,944 KB |
testcase_09 | AC | 8 ms
6,944 KB |
testcase_10 | AC | 6 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 3 ms
6,944 KB |
testcase_13 | AC | 9 ms
6,940 KB |
testcase_14 | AC | 9 ms
6,940 KB |
testcase_15 | AC | 7 ms
6,944 KB |
testcase_16 | AC | 6 ms
6,940 KB |
testcase_17 | AC | 4 ms
6,940 KB |
testcase_18 | AC | 7 ms
6,940 KB |
testcase_19 | AC | 9 ms
6,940 KB |
testcase_20 | AC | 4 ms
6,944 KB |
testcase_21 | AC | 7 ms
6,940 KB |
testcase_22 | AC | 4 ms
6,940 KB |
testcase_23 | AC | 8 ms
6,940 KB |
testcase_24 | AC | 9 ms
6,944 KB |
testcase_25 | AC | 9 ms
6,940 KB |
testcase_26 | AC | 7 ms
6,944 KB |
testcase_27 | AC | 8 ms
6,940 KB |
testcase_28 | AC | 7 ms
6,940 KB |
testcase_29 | AC | 4 ms
6,944 KB |
testcase_30 | AC | 3 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 3 ms
6,944 KB |
testcase_38 | AC | 4 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 3 ms
6,940 KB |
testcase_41 | AC | 4 ms
6,940 KB |
testcase_42 | AC | 4 ms
6,940 KB |
testcase_43 | AC | 4 ms
6,944 KB |
testcase_44 | AC | 7 ms
6,944 KB |
testcase_45 | AC | 6 ms
6,940 KB |
testcase_46 | AC | 8 ms
6,940 KB |
testcase_47 | AC | 8 ms
6,944 KB |
testcase_48 | AC | 7 ms
6,940 KB |
testcase_49 | AC | 7 ms
6,944 KB |
testcase_50 | AC | 3 ms
6,940 KB |
testcase_51 | AC | 7 ms
6,944 KB |
testcase_52 | AC | 4 ms
6,944 KB |
testcase_53 | AC | 9 ms
6,940 KB |
testcase_54 | AC | 2 ms
6,944 KB |
testcase_55 | AC | 2 ms
6,944 KB |
testcase_56 | AC | 2 ms
6,940 KB |
testcase_57 | AC | 2 ms
6,940 KB |
testcase_58 | AC | 2 ms
6,944 KB |
testcase_59 | AC | 2 ms
6,940 KB |
testcase_60 | AC | 2 ms
6,940 KB |
testcase_61 | AC | 2 ms
6,940 KB |
testcase_62 | AC | 2 ms
6,940 KB |
testcase_63 | AC | 2 ms
6,940 KB |
testcase_64 | AC | 2 ms
6,940 KB |
testcase_65 | AC | 2 ms
6,948 KB |
testcase_66 | AC | 2 ms
6,944 KB |
testcase_67 | AC | 2 ms
6,940 KB |
testcase_68 | AC | 2 ms
6,940 KB |
testcase_69 | AC | 4 ms
6,940 KB |
testcase_70 | AC | 4 ms
6,948 KB |
testcase_71 | AC | 5 ms
6,940 KB |
testcase_72 | AC | 3 ms
6,940 KB |
testcase_73 | AC | 4 ms
6,944 KB |
testcase_74 | AC | 5 ms
6,944 KB |
testcase_75 | AC | 5 ms
6,940 KB |
testcase_76 | AC | 9 ms
6,940 KB |
testcase_77 | AC | 10 ms
6,940 KB |
testcase_78 | AC | 2 ms
6,940 KB |
testcase_79 | AC | 10 ms
6,944 KB |
testcase_80 | AC | 8 ms
6,944 KB |
testcase_81 | AC | 8 ms
6,944 KB |
testcase_82 | AC | 6 ms
6,944 KB |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1069" #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()); { set<int>a; auto[dist, path] = this->dijkstra(s, t, a); this->A.emplace_back(path); this->distance.emplace_back(dist); } while (A.size() < this->K) { if (A.size() == 10) { int akjakldj = 10; } const auto last_path = this->A.back(); vector<int> spur_root; T now_distance = 0; set<int> used_node; 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; this->removed_edge[edge_idx] = true; used_node.insert(edge.u); vector<int> rem; for (int j = 0; j < i; ++j) { this->removed_edge[last_path[j]] = true; rem.emplace_back(last_path[j]); } 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, used_node); 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; } if (B.empty()) { break; } 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 set<int> &used_node) 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 (used_node.find(v) != used_node.end()) { continue; } 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<long 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; // FOE(r, ksp.k_shortest_path(i)) { // cout << ksp.get_edge(r).u << "->" << ksp.get_edge(r).v << ", "; // } // cout << endl; } else { cout << -1 << endl; } } return 0; }