結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:46:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 416 ms / 2,000 ms |
コード長 | 2,103 bytes |
コンパイル時間 | 1,032 ms |
コンパイル使用メモリ | 97,216 KB |
実行使用メモリ | 37,404 KB |
最終ジャッジ日時 | 2024-11-06 03:29:41 |
合計ジャッジ時間 | 9,811 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
#include <iostream>#include<vector>#include<algorithm>#include<string>#include<map>#include<set>#include<stack>#include<queue>#include<math.h>using namespace std;typedef long long ll;#define int long long#define ld long doubletypedef vector<ld> VI;typedef pair<ld, ld> pii;typedef vector<pii> VP;typedef vector<string> VS;typedef priority_queue<int> PQ;template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }#define fore(i,a) for(auto &i:a)#define REP(i,n) for(int i=0;i<n;i++)#define eREP(i,n) for(int i=0;i<=n;i++)#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)#define SORT(c) sort((c).begin(),(c).end())#define rSORT(c) sort((c).rbegin(),(c).rend())#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))#define INF 1000000000#define LLINF 922337203685477807#define mod 1000000007//priority_queue<int,vector<int>, greater<int> > q2;int N, M;int X, Y;struct edge {int to;ld cost;};vector<vector<edge> > G;VI d;void dikstra(int s) {priority_queue<pii, vector<pii>, greater<pii> >que;REP(i, N)d[i] = LLINF;d[s] = 0;que.push(pii(0, s));while (!que.empty()) {pii p = que.top();que.pop();int v = p.second;if (d[v] < p.first)continue;REP(i, G[v].size()) {edge e = G[v][i];if (d[e.to] > d[v] + e.cost) {d[e.to] = d[v] + e.cost;que.push(pii(d[e.to], e.to));}}}}ld dd(pii a, pii b) {return pow((a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second),0.5);}signed main() {cin.tie(0);ios::sync_with_stdio(false);cin >> N >> M;G.resize(N);d.resize(N);cin >> X >> Y;X--; Y--;VP A(N);REP(i, N)cin >> A[i].first >> A[i].second;REP(i, M) {int u, v; cin >> u >> v; u--; v--;ld dis = dd(A[u], A[v]);G[u].push_back((edge) { v, dis });G[v].push_back((edge) { u, dis });}dikstra(X);printf("%.15Lf\n", d[Y]);return 0;}