結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
![]() |
提出日時 | 2020-05-29 22:06:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 337 ms / 2,000 ms |
コード長 | 1,986 bytes |
コンパイル時間 | 2,820 ms |
コンパイル使用メモリ | 206,616 KB |
最終ジャッジ日時 | 2025-01-10 17:21:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> #define FASTIO using namespace std; using ll = long long; using Vi = vector<int>; using Vl = vector<ll>; using Pii = pair<int, int>; using Pll = pair<ll, ll>; constexpr int I_INF = numeric_limits<int>::max(); constexpr ll L_INF = numeric_limits<ll>::max(); //%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% struct Pos { double x, y; }; double distance(const Pos& a, const Pos& b) { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } constexpr double D_INF = 1e20; using Pid = pair<int, double>; using Pdi = pair<double, int>; using Graph = vector<vector<Pid>>; void solve() { ll N, M, X, Y; cin >> N >> M >> X >> Y; --X, --Y; vector<Pos> poss(N); for (ll i = 0; i < N; i++) { cin >> poss[i].x >> poss[i].y; } Graph g(N); for (ll i = 0; i < M; i++) { ll a, b; cin >> a >> b; --a, --b; double c = distance(poss[a], poss[b]); g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector<double> dist(N, D_INF); dist[X] = 0.0; priority_queue<Pdi, vector<Pdi>, greater<Pdi>> q; q.emplace(0.0, X); while (!q.empty()) { auto [cost, idx] = q.top(); q.pop(); if (dist[idx] < cost) continue; for (const auto& [to, c] : g[idx]) { double ncost = cost + c; if (ncost >= dist[to]) continue; dist[to] = ncost; q.emplace(ncost, to); } } cout << setprecision(20) << dist[Y] << "\n"; } //%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% int main() { #ifdef FASTIO cin.tie(0), cout.tie(0); ios::sync_with_stdio(false); #endif #ifdef FILEINPUT ifstream ifs("./in_out/input.txt"); cin.rdbuf(ifs.rdbuf()); #endif #ifdef FILEOUTPUT ofstream ofs("./in_out/output.txt"); cout.rdbuf(ofs.rdbuf()); #endif solve(); cout << flush; return 0; }