結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | beet |
提出日時 | 2020-05-29 21:29:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 1,820 bytes |
コンパイル時間 | 2,719 ms |
コンパイル使用メモリ | 205,432 KB |
実行使用メモリ | 23,424 KB |
最終ジャッジ日時 | 2024-04-23 20:15:06 |
合計ジャッジ時間 | 7,438 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 91 ms
13,696 KB |
testcase_03 | AC | 131 ms
21,872 KB |
testcase_04 | AC | 136 ms
21,872 KB |
testcase_05 | AC | 94 ms
21,616 KB |
testcase_06 | AC | 96 ms
21,792 KB |
testcase_07 | AC | 37 ms
8,704 KB |
testcase_08 | AC | 133 ms
22,784 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 58 ms
12,032 KB |
testcase_11 | AC | 41 ms
9,472 KB |
testcase_12 | AC | 22 ms
7,296 KB |
testcase_13 | AC | 95 ms
14,864 KB |
testcase_14 | AC | 108 ms
17,368 KB |
testcase_15 | AC | 129 ms
19,160 KB |
testcase_16 | AC | 58 ms
11,588 KB |
testcase_17 | AC | 141 ms
20,488 KB |
testcase_18 | AC | 42 ms
9,472 KB |
testcase_19 | AC | 132 ms
19,528 KB |
testcase_20 | AC | 35 ms
8,192 KB |
testcase_21 | AC | 49 ms
10,752 KB |
testcase_22 | AC | 121 ms
18,224 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 3 ms
5,376 KB |
testcase_25 | AC | 20 ms
7,168 KB |
testcase_26 | AC | 70 ms
12,736 KB |
testcase_27 | AC | 71 ms
12,664 KB |
testcase_28 | AC | 123 ms
18,716 KB |
testcase_29 | AC | 13 ms
6,272 KB |
testcase_30 | AC | 129 ms
20,156 KB |
testcase_31 | AC | 91 ms
16,312 KB |
testcase_32 | AC | 55 ms
11,340 KB |
testcase_33 | AC | 133 ms
20,900 KB |
testcase_34 | AC | 45 ms
9,600 KB |
testcase_35 | AC | 136 ms
20,596 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 3 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 212 ms
23,424 KB |
testcase_42 | AC | 56 ms
9,856 KB |
testcase_43 | AC | 101 ms
14,080 KB |
testcase_44 | AC | 34 ms
7,552 KB |
testcase_45 | AC | 94 ms
13,952 KB |
testcase_46 | AC | 2 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; template<typename T> struct Dijkstra{ struct Edge{ int to; T cost; Edge(int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; vector< vector<Edge> > G; vector<T> ds; vector<int> bs; Dijkstra(int n):G(n){} void add_edge(int u,int v,T c){ G[u].emplace_back(v,c); } void build(int s){ int n=G.size(); ds.assign(n,numeric_limits<T>::max()); bs.assign(n,-1); priority_queue<Edge> pq; ds[s]=0; pq.emplace(s,ds[s]); while(!pq.empty()){ auto p=pq.top();pq.pop(); int v=p.to; if(ds[v]<p.cost) continue; for(auto e:G[v]){ if(ds[e.to]>ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } T operator[](int k){return ds[k];} vector<int> restore(int to){ vector<int> res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; struct Precision{ Precision(){ cout<<fixed<<setprecision(12); } }precision_beet; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; int x,y; cin>>x>>y; x--;y--; using D = double; vector<D> ps(n),qs(n); for(int i=0;i<n;i++) cin>>ps[i]>>qs[i]; Dijkstra<D> G(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; D d=hypot(ps[u]-ps[v],qs[u]-qs[v]); G.add_edge(u,v,d); G.add_edge(v,u,d); } G.build(x); cout<<G[y]<<newl; return 0; }