結果
問題 | 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; }