結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
![]() |
提出日時 | 2020-05-29 21:39:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 275 ms / 2,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 1,093 ms |
コンパイル使用メモリ | 102,868 KB |
実行使用メモリ | 25,248 KB |
最終ジャッジ日時 | 2024-11-06 02:55:09 |
合計ジャッジ時間 | 6,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> using namespace std; typedef long long ll; const double INF = 1e+15; typedef pair<double, int> P; struct edge{ int to; double cost; }; double d[200000]; void dijkstra(int s, int num_v, vector<edge> G[]){ priority_queue<P, vector<P>, greater<P>> que; fill(d, d+num_v, INF); d[s] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top();que.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0; i < G[v].size(); i++){ edge e = G[v][i]; if(d[v] + e.cost < d[e.to]){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } double dist(double xa, double xb, double ya, double yb){ return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb)); } vector<edge> G[200000]; int N, M, X, Y; double p[200000], q[200000]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> M >> X >> Y; X--; Y--; for(int i = 0; i < N; i++) cin >> p[i] >> q[i]; for(int i = 0; i < M; i++){ int P, Q; cin >> P >> Q; P--; Q--; G[P].push_back((edge){Q, dist(p[P], p[Q], q[P], q[Q])}); G[Q].push_back((edge){P, dist(p[P], p[Q], q[P], q[Q])}); } dijkstra(X, N, G); cout << d[Y] << endl; }