結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
|
提出日時 | 2020-05-29 21:37:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 320 ms / 2,000 ms |
コード長 | 1,891 bytes |
コンパイル時間 | 2,288 ms |
コンパイル使用メモリ | 179,940 KB |
実行使用メモリ | 34,956 KB |
最終ジャッジ日時 | 2024-11-06 02:51:33 |
合計ジャッジ時間 | 8,601 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long double;constexpr char newl = '\n';struct State {int at;ll cost;//int prev;State(int at, ll cost/*, int prev*/) : at(at), cost(cost)/*, prev(prev)*/ {}bool operator>(const State& s) const {return cost > s.cost;}};struct Edge {int to;ll cost;Edge(int to, ll cost) : to(to), cost(cost) {}};using Graph = vector< vector<Edge> >; //隣接リストconst ll INF = 1e15;//const int NONE = -1;//sは始点、mincは最短経路のコスト、prevsは最短経路をたどる際の前の頂点void dijkstra(int s, const Graph& graph, vector<ll>& minc/*, vector<int>& prevs*/){minc.assign(graph.size(), INF);//prevs.assign(graph.size(), NONE);priority_queue<State, vector<State>, greater<State> > pq;pq.emplace(s, 0/*, NONE*/);minc[s] = 0;while(!pq.empty()) {State cur = pq.top();pq.pop();if (minc[cur.at] < cur.cost) continue;for(const Edge& e : graph[cur.at]) {ll cost = cur.cost + e.cost;if (minc[e.to] <= cost) continue;minc[e.to] = cost;//prevs[e.to] = cur.at;pq.emplace(e.to, cost/*, cur.at*/);}}}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n, m;cin >> n >> m;int x, y;cin >> x >> y;--x; --y;vector<double> p(n), q(n);for (int i = 0; i < n; i++) {cin >> p[i] >> q[i];}Graph g(n);for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;--u; --v;ll cost = hypot(p[u] - p[v], q[u] - q[v]);g[u].emplace_back(v, cost);g[v].emplace_back(u, cost);}vector<ll> minc;dijkstra(x, g, minc);cout << fixed << setprecision(15) << minc[y] << newl;return 0;}