結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | QCFium |
提出日時 | 2020-05-29 22:45:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 173,820 KB |
実行使用メモリ | 20,992 KB |
最終ジャッジ日時 | 2024-04-24 00:14:34 |
合計ジャッジ時間 | 7,330 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 89 ms
12,288 KB |
testcase_03 | AC | 129 ms
20,148 KB |
testcase_04 | AC | 143 ms
20,152 KB |
testcase_05 | AC | 106 ms
20,156 KB |
testcase_06 | AC | 108 ms
20,024 KB |
testcase_07 | AC | 35 ms
7,964 KB |
testcase_08 | AC | 127 ms
20,224 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 56 ms
10,880 KB |
testcase_11 | AC | 40 ms
8,576 KB |
testcase_12 | AC | 31 ms
7,040 KB |
testcase_13 | AC | 112 ms
13,880 KB |
testcase_14 | AC | 126 ms
16,056 KB |
testcase_15 | AC | 150 ms
17,764 KB |
testcase_16 | AC | 76 ms
11,168 KB |
testcase_17 | AC | 176 ms
18,764 KB |
testcase_18 | AC | 52 ms
8,960 KB |
testcase_19 | AC | 149 ms
18,004 KB |
testcase_20 | AC | 39 ms
7,552 KB |
testcase_21 | AC | 64 ms
10,668 KB |
testcase_22 | AC | 136 ms
16,824 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 3 ms
5,376 KB |
testcase_25 | AC | 29 ms
6,912 KB |
testcase_26 | AC | 72 ms
11,420 KB |
testcase_27 | AC | 77 ms
12,000 KB |
testcase_28 | AC | 136 ms
17,400 KB |
testcase_29 | AC | 19 ms
6,144 KB |
testcase_30 | AC | 135 ms
18,672 KB |
testcase_31 | AC | 107 ms
15,172 KB |
testcase_32 | AC | 55 ms
10,080 KB |
testcase_33 | AC | 150 ms
19,336 KB |
testcase_34 | AC | 56 ms
8,960 KB |
testcase_35 | AC | 134 ms
19,008 KB |
testcase_36 | AC | 3 ms
5,376 KB |
testcase_37 | AC | 4 ms
5,376 KB |
testcase_38 | AC | 3 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 251 ms
20,992 KB |
testcase_42 | AC | 56 ms
8,732 KB |
testcase_43 | AC | 101 ms
12,672 KB |
testcase_44 | AC | 30 ms
7,152 KB |
testcase_45 | AC | 110 ms
12,416 KB |
testcase_46 | AC | 2 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
ソースコード
#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; }