結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
|
提出日時 | 2020-05-29 22:50:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 277 ms / 2,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 8,227 ms |
コンパイル使用メモリ | 166,260 KB |
最終ジャッジ日時 | 2025-01-10 18:07:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <algorithm> #include <vector> #include <iomanip> #include <random> #include <set> #include <queue> #define REP(i, n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; constexpr ll INF = 1LL << 60; int n, m, x, y; // O(|V|+|E|)log|V|) void dijkstra(int s, vector<vector<pair<int, double>>> &g, vector<double> &dist) { using Info = pair<double, int>; // init dist.assign(g.size(), 1e18); dist[s] = 0.0; priority_queue<Info, vector<Info>, greater<Info>> pq; pq.emplace(0.0, s); // // main while (!pq.empty()) { double d = pq.top().first; int v = pq.top().second; pq.pop(); if (dist[v] < d) continue; for (auto e : g[v]) { if (dist[e.first] > dist[v] + e.second) { dist[e.first] = dist[v] + e.second; pq.emplace(dist[e.first], e.first); } } } // } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> x >> y; --x, --y; vector<pair<double, double>> pos; REP(i, n) { double p, q; cin >> p >> q; pos.emplace_back(p, q); } vector<vector<pair<int, double>>> g(n); REP(i, m) { int p, q; cin >> p >> q; --p, --q; double X = pos[p].first - pos[q].first; double Y = pos[p].second - pos[q].second; double cost = sqrt(X * X + Y * Y); g[q].emplace_back(p, cost); g[p].emplace_back(q, cost); } vector<double> dist; dijkstra(x, g, dist); cout << fixed << setprecision(10) << dist[y] << '\n'; return 0; }