#489159 (C++14) No.1065 電柱 / Pole (Easy)

提出ソース

結果

問題	No.1065 電柱 / Pole (Easy)
ユーザー	ok
提出日時	2020-05-29 23:21:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	238 ms / 2,000 ms
コード長	1,646 bytes
コンパイル時間	1,253 ms
コンパイル使用メモリ	100,444 KB
実行使用メモリ	33,760 KB
最終ジャッジ日時	2024-04-24 01:26:53
合計ジャッジ時間	7,042 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	98 ms 17,536 KB
testcase_03	AC	139 ms 32,804 KB
testcase_04	AC	136 ms 32,800 KB
testcase_05	AC	102 ms 33,760 KB
testcase_06	AC	104 ms 33,192 KB
testcase_07	AC	31 ms 10,368 KB
testcase_08	AC	111 ms 29,576 KB
testcase_09	AC	11 ms 6,944 KB
testcase_10	AC	50 ms 15,104 KB
testcase_11	AC	34 ms 11,392 KB
testcase_12	AC	23 ms 11,008 KB
testcase_13	AC	106 ms 21,152 KB
testcase_14	AC	127 ms 25,280 KB
testcase_15	AC	159 ms 27,204 KB
testcase_16	AC	71 ms 17,044 KB
testcase_17	AC	166 ms 29,244 KB
testcase_18	AC	47 ms 13,456 KB
testcase_19	AC	161 ms 27,540 KB
testcase_20	AC	35 ms 9,716 KB
testcase_21	AC	59 ms 16,456 KB
testcase_22	AC	140 ms 27,400 KB
testcase_23	AC	3 ms 6,940 KB
testcase_24	AC	3 ms 6,944 KB
testcase_25	AC	22 ms 10,496 KB
testcase_26	AC	77 ms 17,804 KB
testcase_27	AC	82 ms 17,880 KB
testcase_28	AC	150 ms 27,544 KB
testcase_29	AC	16 ms 8,064 KB
testcase_30	AC	155 ms 30,484 KB
testcase_31	AC	106 ms 25,056 KB
testcase_32	AC	61 ms 15,540 KB
testcase_33	AC	158 ms 30,772 KB
testcase_34	AC	55 ms 13,320 KB
testcase_35	AC	163 ms 31,384 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	3 ms 6,940 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	3 ms 6,944 KB
testcase_40	AC	2 ms 6,944 KB
testcase_41	AC	238 ms 30,968 KB
testcase_42	AC	53 ms 12,032 KB
testcase_43	AC	114 ms 18,280 KB
testcase_44	AC	38 ms 9,088 KB
testcase_45	AC	120 ms 17,664 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;


void dijkstra(int s, vector<long double> &d, vector<vector<pair<int,long double>>> &G){
	priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int>>> q;
	
	d.clear();
	d.resize(G.size(),INF);
	d[s] = 0;
	q.push(make_pair(0,s));
	
	while(!q.empty()){
		pair<long double,int> p = q.top();q.pop();
		int v = p.second;
		
		if(d[v] < p.first) continue;
		
		for(pair<int,long double> e : G[v]){
			if(d[e.first] > d[v] + e.second){
				d[e.first] = d[v] + e.second;
				q.push(make_pair(d[e.first],e.first));
			}
		}
	}	
}

long double dis(vector<pair<int,int>> &p, int a, int b){
	long double x = (p[a].first - p[b].first);
	long double y = (p[a].second - p[b].second);
	
	return sqrt(x * x + y * y);
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	int N, M;
	int X, Y;
	vector<pair<int,int>> p;
	vector<vector<pair<int,long double>>> G;
	vector<long double> d; 
	cin>>N>>M;
	
	cin>>X>>Y;
	
	X--, Y--;
	
	p.resize(N);
	G.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>p[i].first>>p[i].second;
	}
	
	for(int i = 0; i < M; i++){
		int P, Q;
		
		cin>>P>>Q;
		
		P--, Q--;
		
		G[P].push_back({Q, dis(p, P, Q)});
		G[Q].push_back({P, dis(p, P, Q)});
	}
	
	dijkstra(X, d, G);
	
	
	cout<<d[Y]<<endl;
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード