結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:47:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 495 ms / 2,000 ms |
コード長 | 2,484 bytes |
コンパイル時間 | 3,162 ms |
コンパイル使用メモリ | 206,520 KB |
最終ジャッジ日時 | 2025-01-10 16:54:50 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF_LL 100000000000000000LL #define INF 200000000 #define MOD 1000000007 #define ll long long #define all(x) x.begin(), x.end() #define REP(i, a, b) for(int i = a; i < b; i++) #define rep(i, n) REP(i, 0, n) // typedef float double; // typedef priority_queue prique; typedef pair<double, int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<P> vp; typedef vector<ll> vl; typedef vector<vi> matrix; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int sign[2] = {1, -1}; template <class T> bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, T b) { if(a > b) { a = b; return 1; } return 0; } ll modpow(ll a, ll b, ll m) { if(b == 0) return 1; ll t = modpow(a, b / 2, m); if(b & 1) { return (t * t % m) * a % m; } else { return t * t % m; } } // struct edge { // int to; // ll cost; // edge(int t, ll c) { to = t, cost = c; } // }; struct edge { int to; double cost; edge(int t, double c) { to = t, cost = c; } }; vector<double> dijkstra(vector<vector<edge>> &g, int start, int n) { priority_queue<P, vector<P>, greater<P>> que; vector<double> dist(n, INF_LL); dist[start] = 0; que.push(P(0, start)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first) continue; rep(i, (int)g[v].size()) { edge e = g[v][i]; if(dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; que.push(P(dist[e.to], e.to)); } } } return dist; } signed main() { int n, m, x, y; cin >> n >> m >> x >> y; x--; y--; vector<pair<int, int>> a(n); rep(i, n) cin >> a[i].first >> a[i].second; vector<vector<edge>> g(n); rep(i, m) { int p, q; cin >> p >> q; double t = sqrt((a[p - 1].first - a[q - 1].first) * (a[p - 1].first - a[q - 1].first) + (a[p - 1].second - a[q - 1].second) * (a[p - 1].second - a[q - 1].second)); g[p - 1].push_back({q - 1, t}); g[q - 1].push_back({p - 1, t}); } vector<double> dist = dijkstra(g, x, n); cout << fixed << setprecision(15) << dist[y] << endl; return 0; }