結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:51:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 2,796 bytes |
コンパイル時間 | 2,883 ms |
コンパイル使用メモリ | 209,832 KB |
最終ジャッジ日時 | 2025-01-10 17:00:36 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; using CostType = double; struct Edge { int src, dst; CostType cost; Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {} inline bool operator<(const Edge &x) const { return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src; } inline bool operator<=(const Edge &x) const { return !(x < *this); } inline bool operator>(const Edge &x) const { return x < *this; } inline bool operator>=(const Edge &x) const { return !(*this < x); } }; struct Dijkstra { using Pci = pair<CostType, int>; Dijkstra(const vector<vector<Edge>> &graph, const CostType CINF) : graph(graph), CINF(CINF) {} vector<CostType> build(int s) { int n = graph.size(); vector<CostType> dist(n, CINF); dist[s] = 0; prev.assign(n, -1); priority_queue<Pci, vector<Pci>, greater<Pci>> que; que.emplace(0, s); while (!que.empty()) { CostType cost; int ver; tie(cost, ver) = que.top(); que.pop(); if (dist[ver] < cost) continue; for (const Edge &e : graph[ver]) { if (dist[e.dst] > dist[ver] + e.cost) { dist[e.dst] = dist[ver] + e.cost; prev[e.dst] = ver; que.emplace(dist[e.dst], e.dst); } } } return dist; } vector<int> build_path(int t) { vector<int> res; for (; t != -1; t = prev[t]) res.emplace_back(t); reverse(ALL(res)); return res; } private: vector<vector<Edge>> graph; const CostType CINF; vector<int> prev; }; int main() { int n, m, x, y; cin >> n >> m >> x >> y; --x; --y; vector<int> p(n), q(n); REP(i, n) cin >> p[i] >> q[i]; vector<vector<Edge>> graph(n); while (m--) { int P, Q; cin >> P >> Q; --P; --Q; double dist = sqrt((p[P] - p[Q]) * (p[P] - p[Q]) + (q[P] - q[Q]) * (q[P] - q[Q])); graph[P].emplace_back(P, Q, dist); graph[Q].emplace_back(Q, P, dist); } Dijkstra dij(graph, LINF); cout << dij.build(x)[y] << '\n'; return 0; }