結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:45:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 1,816 ms |
コンパイル使用メモリ | 178,916 KB |
実行使用メモリ | 21,368 KB |
最終ジャッジ日時 | 2024-11-06 06:44:09 |
合計ジャッジ時間 | 7,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#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 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)}); } auto dijkstra = [&] (int s, int t) { 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 (dist[k.first] > j.first + k.second) que.push({dist[k.first] = j.first + k.second, k.first}); } } return dist[t]; }; printf("%.11f\n", dijkstra(x, y)); return 0; }