結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
![]() |
提出日時 | 2021-02-17 15:56:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 2,456 ms |
コンパイル使用メモリ | 206,580 KB |
最終ジャッジ日時 | 2025-01-18 21:49:46 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:21:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 21 | REP(i, N) scanf("%d %d", &y[i], &x[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~ main.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d %d", &P, &Q); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) begin(v),end(v) template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using pii = pair<int, int>; constexpr ll INF = 1ll<<30; constexpr ll longINF = 1ll<<60; constexpr ll MOD = 1000000007; constexpr bool debug = false; //---------------------------------// int main() { int N, M, X, Y; cin >> N >> M >> X >> Y; --X; --Y; vector<int> y(N), x(N); REP(i, N) scanf("%d %d", &y[i], &x[i]); vector<vector<pair<int, double>>> g(N); REP(i, M) { int P, Q; scanf("%d %d", &P, &Q); --P; --Q; const double l = hypot(x[P] - x[Q], y[P] - y[Q]); g[P].emplace_back(Q, l); g[Q].emplace_back(P, l); } using tup = tuple<double, int>; vector<double> dist(N, INF); priority_queue<tup, vector<tup>, greater<tup>> pq; dist[X] = 0; pq.emplace(0, X); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] != d) continue; for (auto [v, c] : g[u]) if (chmin(dist[v], d + c)) pq.emplace(dist[v], v); } printf("%.18f\n", dist[Y]); }