結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:11:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,419 ms / 2,000 ms |
コード長 | 2,485 bytes |
コンパイル時間 | 2,264 ms |
コンパイル使用メモリ | 190,700 KB |
実行使用メモリ | 6,996 KB |
最終ジャッジ日時 | 2024-07-23 15:05:45 |
合計ジャッジ時間 | 25,377 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 79 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >; const double DINF = 1000000000; int main() { int n = ri(); int m = ri(); int k = ri(); int x = ri() - 1, y = ri() - 1; std::pair<int, int> pts[n]; for (auto &i : pts) i.first = ri(), i.second = ri(); auto calc_dist = [&] (int i, int j) { return std::hypot(pts[i].first - pts[j].first, pts[i].second - pts[j].second); }; std::vector<std::pair<int, double> > hen[n]; for (int i = 0; i < m; i++) { int x = ri() - 1; int y = ri() - 1; hen[x].push_back({y, calc_dist(x, y)}); hen[y].push_back({x, calc_dist(x, y)}); } struct Payload { double cur_cost; int pos; std::vector<bool> used; bool operator > (const Payload &rhs) const { return cur_cost > rhs.cur_cost; } bool operator < (const Payload &rhs) const { return cur_cost < rhs.cur_cost; } }; auto dijkstra = [&] (int s, int t, const std::vector<bool> &used) { std::vector<double> dist(n, DINF); pqueue_inv<std::pair<double, int> > que; que.push({dist[s] = 0, s}); while (que.size()) { auto j = que.top(); que.pop(); if (j.second == t) return dist[t]; if (j.first != dist[j.second]) continue; for (auto k : hen[j.second]) { if (used[k.first]) continue; if (dist[k.first] > j.first + k.second) que.push({dist[k.first] = j.first + k.second, k.first}); } } return dist[t]; }; if (dijkstra(x, y, std::vector<bool>(n)) == DINF) { for (int i = 0; i < k; i++) puts("-1"); return 0; } pqueue_inv<std::pair<double, Payload> > que; std::vector<std::pair<double, Payload> > all[n]; std::vector<bool> init_(n); init_[x] = true; que.push({dijkstra(x, y, std::vector<bool>(n)), {0, x, init_}}); while (que.size()) { auto i = que.top(); que.pop(); double cur_cost = i.second.cur_cost; int x = i.second.pos; auto &used = i.second.used; if ((int) all[x].size() >= k) continue; all[x].push_back(i); for (auto j : hen[x]) { if (used[j.first]) continue; used[j.first] = true; double cost = dijkstra(j.first, y, used); if (cost == DINF) continue; double new_estimated = cost + cur_cost + j.second; que.push({new_estimated, {cur_cost + j.second, j.first, used}}); // bfs used[j.first] = false; } } for (int i = 0; i < k; i++) { if (i < (int) all[y].size()) { printf("%.11f\n", all[y][i].first); } else puts("-1"); } return 0; }