結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | otamay6 |
提出日時 | 2020-05-29 21:46:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 422 ms / 2,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 176,784 KB |
実行使用メモリ | 23,128 KB |
最終ジャッジ日時 | 2024-11-06 03:30:27 |
合計ジャッジ時間 | 9,866 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h> #define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() #define rAll(x) (x).rbegin(),(x).rend() using namespace std; using ll = long long; int main(){ int N,M; cin>>N>>M; int X,Y; cin>>X>>Y; X--;Y--; vector<double> p(N),q(N); REP(i,N) cin>>p[i]>>q[i]; using P = pair<double,int> ; vector<vector<P>> graph(N); REP(i,M){ int a,b; cin>>a>>b; a--;b--; double c = sqrt(pow(p[a]-p[b],2) + pow(q[a]-q[b],2)); graph[a].push_back(P(c,b)); graph[b].push_back(P(c,a)); } vector<double> dist(N,1e9); priority_queue<P,vector<P>,greater<>> que; dist[X]=0; que.push(P(0,X)); while(!que.empty()){ P p=que.top();que.pop(); int u=p.second; if(dist[u]<p.first) continue; REP(j,graph[u].size()){ int v=graph[u][j].second; double alt=dist[u]+graph[u][j].first; if(dist[v]>alt){ dist[v]=alt; que.push(P(alt,v)); } } } printf("%.16f\n",dist[Y]); }