結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
|
提出日時 | 2020-05-29 21:44:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 1,681 bytes |
コンパイル時間 | 1,819 ms |
コンパイル使用メモリ | 182,640 KB |
実行使用メモリ | 18,784 KB |
最終ジャッジ日時 | 2024-11-06 03:22:09 |
合計ジャッジ時間 | 10,075 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using tp3 = tuple<int, int, int>; using Mat = vector<vector<ll>>; constexpr int INF = 1 << 28; constexpr ll INFL = 1ll << 60; constexpr int dh[4] = { 0,1,0,-1 }; constexpr int dw[4] = { -1,0,1,0 }; bool isin(const int H, const int W, const int h, const int w) { return 0 <= h && h < H && 0 <= w && w < W; } // ============ template finished ============ using pdd = pair<double, double>; using pdi = pair<double, int>; double dist(const vector<pdd>& pq, const int from, const int to) { pdd d = { pq[to].first - pq[from].first,pq[to].second - pq[from].second }; return sqrt(d.first*d.first + d.second*d.second); } int main() { int N, M, X, Y; cin >> N >> M >> X >> Y; X--; Y--; vector<pdd> poss(N); vector<vector<int>> edges(N); rep(i, N)cin >> poss[i].first >> poss[i].second; rep(i, M) { int P, Q; cin >> P >> Q; P--; Q--; edges[P].push_back(Q); edges[Q].push_back(P); } vector<double> ds(N, INFL); priority_queue<pdi, vector<pdi>, greater<pdi>> pq; ds[X] = 0; pq.push({ 0,X }); while (!pq.empty()) { double d; int now; tie(d, now) = pq.top(); pq.pop(); for (auto next : edges[now]) { double nd = d + dist(poss, now, next); if (nd < ds[next]) { ds[next] = nd; pq.push({ nd,next }); } } } cout << fixed << setprecision(12) << ds[Y] << endl; return 0; }