제출 #566194

#제출 시각아이디문제언어결과실행 시간메모리
566194RifalEvacuation plan (IZhO18_plan)C++14
23 / 100
785 ms35092 KiB
#include <bits/stdc++.h> #include <fstream> #define endl '\n' #define mod 32768 #define INF 100000000000000 //#define ll long long //#define cin fin //#define cout fout using namespace std; //ofstream fout("convention.out"); //ifstream fin("convention.in"); const int M = 1e5 + 5; long long arr[M]; vector<pair<int,long long>> v[M]; void d(int s) { for(int i = 0; i < M; i++) { arr[i] = INF; } arr[s] = 0; priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long,int>>> pq; pq.push({arr[s],s}); while(!pq.empty()) { pair<long long,int> tp = pq.top(); pq.pop(); if(arr[tp.second] < tp.first) continue; for(auto i : v[tp.second]) { if(arr[tp.second]+i.second < arr[i.first]) { arr[i.first] = arr[tp.second]+i.second; pq.push({arr[i.first],i.first}); } } } } int main() { int n, m, k, q; cin >> n >> m; for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; v[a].push_back({b,c}); v[b].push_back({a,c}); } cin >> k; int a[k]; for(int i = 0; i < k; i++) { cin >> a[i]; v[0].push_back({a[i],0}); v[a[i]].push_back({0,0}); } d(0); cin >> q; while(q--) { int s, t; cin >> s >> t; cout << min(arr[s],arr[t]) << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...