結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 22:45:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 1,816 ms |
コンパイル使用メモリ | 178,916 KB |
実行使用メモリ | 21,368 KB |
最終ジャッジ日時 | 2024-11-06 06:44:09 |
合計ジャッジ時間 | 7,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >;const double DINF = 1000000000;int main() {int n = ri();int m = ri();int x = ri() - 1, y = ri() - 1;std::pair<int, int> pts[n];for (auto &i : pts) i.first = ri(), i.second = ri();auto calc_dist = [&] (int i, int j) {return std::hypot(pts[i].first - pts[j].first, pts[i].second - pts[j].second);};std::vector<std::pair<int, double> > hen[n];for (int i = 0; i < m; i++) {int x = ri() - 1;int y = ri() - 1;hen[x].push_back({y, calc_dist(x, y)});hen[y].push_back({x, calc_dist(x, y)});}auto dijkstra = [&] (int s, int t) {std::vector<double> dist(n, DINF);pqueue_inv<std::pair<double, int> > que;que.push({dist[s] = 0, s});while (que.size()) {auto j = que.top();que.pop();if (j.second == t) return dist[t];if (j.first != dist[j.second]) continue;for (auto k : hen[j.second]) {if (dist[k.first] > j.first + k.second) que.push({dist[k.first] = j.first + k.second, k.first});}}return dist[t];};printf("%.11f\n", dijkstra(x, y));return 0;}