Submission #570145

#TimeUsernameProblemLanguageResultExecution timeMemory
570145SSRSEvacuation plan (IZhO18_plan)C++14
23 / 100
832 ms21372 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1000000000; int main(){ int n, m; cin >> n >> m; vector<vector<pair<int, int>>> E(n); for (int i = 0; i < m; i++){ int a, b, w; cin >> a >> b >> w; a--; b--; E[a].push_back(make_pair(w, b)); E[b].push_back(make_pair(w, a)); } int k; cin >> k; vector<int> g(k); for (int i = 0; i < k; i++){ cin >> g[i]; g[i]--; } vector<int> d(n, -1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < k; i++){ pq.push(make_pair(0, g[i])); } while (!pq.empty()){ int c = pq.top().first; int v = pq.top().second; pq.pop(); if (d[v] == -1){ d[v] = c; for (auto P : E[v]){ int w = P.second; if (d[w] == -1){ pq.push(make_pair(c + P.first, w)); } } } } int Q; cin >> Q; for (int i = 0; i < Q; i++){ int s, t; cin >> s >> t; s--; t--; cout << min(d[s], d[t]) << endl; } }
#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...