結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:18:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 1,342 bytes |
コンパイル時間 | 2,606 ms |
コンパイル使用メモリ | 203,884 KB |
最終ジャッジ日時 | 2025-01-10 17:40:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T, class U> using Pa = pair<T, U>; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M; cin >> N >> M; int S,T; cin >> S >> T; S--; T--; vec<int> P(N),Q(N); for(int i=0;i<N;i++) cin >> P[i] >> Q[i]; auto dist = [&](int i,int j){ double dx = P[i]-P[j],dy = Q[i]-Q[j]; return sqrt(dx*dx+dy*dy); }; vvec<Pa<double,int>> g(N); for(int i=0;i<M;i++){ int a,b; cin >> a >> b; a--; b--; double d = dist(a,b); g[a].push_back({d,b}); g[b].push_back({d,a}); } double inf = 1e9; vec<double> D(N,inf); vec<int> check(N,0); priority_queue<Pa<double,int>,vec<Pa<double,int>>,greater<Pa<double,int>>> que; que.push({0.0,S}); D[S] = 0; while(!que.empty()){ auto [d,cur] = que.top(); que.pop(); if(check[cur]) continue; check[cur] = 1; for(auto& e:g[cur]){ double nd = d+e.first; if(D[e.second]>nd){ D[e.second] = nd; que.push({nd,e.second}); } } } cout << fixed << setprecision(10) << D[T] << "\n"; }