結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:58:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 1,453 bytes |
コンパイル時間 | 1,769 ms |
コンパイル使用メモリ | 175,756 KB |
実行使用メモリ | 27,168 KB |
最終ジャッジ日時 | 2024-11-06 04:34:32 |
合計ジャッジ時間 | 9,720 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; #define MAX_N 200005 struct Edge { int src, dest; double weight; }; bool operator>(const Edge& a, const Edge& b){ return a.weight > b.weight; } int N, M; vector<Edge> G[MAX_N]; double cost[MAX_N]; void dijkstra(int start){ rep(i,N+1){ cost[i] = 1e100; } priority_queue<Edge,vector<Edge>,greater<Edge>> q; q.push((Edge){-1,start,0}); while(!q.empty()){ Edge e=q.top(); q.pop(); if(cost[e.dest] < 1e99) continue; cost[e.dest]=e.weight; FOR(it,G[e.dest]) if(cost[it->dest] > 1e99) q.push((Edge){it->src,it->dest,e.weight+it->weight}); } } int main(){ cin >> N >> M; int X, Y; cin >> X >> Y; vector<pair<int,int>> v; v.emplace_back(0,0); rep(i,N){ int p, q; cin >> p >> q; v.emplace_back(p,q); } rep(i,M){ int p, q; cin >> p >> q; double px = v[p].first; double py = v[p].second; double qx = v[q].first; double qy = v[q].second; double dist = sqrt((px-qx)*(px-qx) + (py-qy)*(py-qy)); G[p].push_back((Edge){p,q,dist}); G[q].push_back((Edge){q,p,dist}); } dijkstra(X); double ret = cost[Y]; printf("%.12lf\n", ret); return 0; }