結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | realDivineJK |
提出日時 | 2020-05-30 00:50:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,624 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 190,236 KB |
実行使用メモリ | 79,172 KB |
最終ジャッジ日時 | 2023-08-06 09:23:23 |
合計ジャッジ時間 | 32,545 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 46 ms
7,848 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 164 ms
17,028 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 698 ms
25,556 KB |
testcase_17 | WA | - |
testcase_18 | AC | 459 ms
19,604 KB |
testcase_19 | WA | - |
testcase_20 | AC | 283 ms
15,204 KB |
testcase_21 | AC | 670 ms
23,912 KB |
testcase_22 | WA | - |
testcase_23 | AC | 6 ms
4,376 KB |
testcase_24 | AC | 8 ms
4,376 KB |
testcase_25 | AC | 149 ms
15,608 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 126 ms
9,932 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | AC | 512 ms
24,592 KB |
testcase_33 | WA | - |
testcase_34 | AC | 469 ms
19,772 KB |
testcase_35 | AC | 1,348 ms
57,012 KB |
testcase_36 | AC | 5 ms
4,376 KB |
testcase_37 | AC | 7 ms
4,376 KB |
testcase_38 | AC | 5 ms
4,380 KB |
testcase_39 | AC | 7 ms
4,380 KB |
testcase_40 | AC | 3 ms
4,380 KB |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 202 ms
13,664 KB |
testcase_45 | WA | - |
testcase_46 | AC | 1 ms
4,380 KB |
testcase_47 | AC | 1 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(void){ // Your code here! int N, M; cin >> N >> M; int X, Y; cin >> X >> Y; X--; Y--; map<int, vector<int>> D; map<long long, double> distD; vector<pair<int, int>> p(N); int x, y; for (int i=0;i<N;i++){ cin >> x >> y; p[i] = make_pair(x, y); } for (int i=0;i<M;i++){ cin >> x >> y; x--; y--; if (D.count(x)){ D[x].push_back(y); } else{ D[x] = {y}; } if (D.count(y)){ D[y].push_back(x); } else{ D[y] = {x}; } distD[x*N+y] = sqrt((p[x].first-p[y].first)*(p[x].first-p[y].first)+(p[x].second-p[y].second)*(p[x].second-p[y].second)); distD[y*N+x] = sqrt((p[x].first-p[y].first)*(p[x].first-p[y].first)+(p[x].second-p[y].second)*(p[x].second-p[y].second)); } priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq; vector<double> dist(N, 1e9); dist[X] = 0.0; for (int i=0;i<N;i++){ pq.push(make_pair(dist[i], i)); } pair<double, int> tmp; int r; while (!pq.empty()){ tmp = pq.top(); pq.pop(); r = tmp.second; if (D.count(r)){ for (int i: D[r]){ if (dist[i] > dist[r] + distD[(long long)r*N+i]){ dist[i] = dist[r] + distD[(long long)r*N+i]; pq.push(make_pair(dist[i], i)); } } } } printf("%.015f\n", dist[Y]); return 0; }