| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 168955 | tourist | Evacuation plan (IZhO18_plan) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define sz(x) (int)x.size()
#define pii pair < int, int >
#define METH ios::sync_with_stdio(0); cin.tie(0);
#define BEGIN cout << "BEGIN" << endl;
#define END cout << "END" << endl;
const int N = 1e5;
const int mod = 1e9 + 7; /// ANOTHER HASH MOD: 228228227
const int prime = 29; /// ANOTHER HASH PRIME: 997
const int INF = 1e9 + 7;
int n, m, k, q;
vector < int > bad, dist(N + 9, INF);
vector < pii > g[N + 9], querry;
inline void purify() {
}
inline void precalc() {
}
void check(int a, int b) {
for (pii i : g[a]) {
if (i.first == b) {
assert(false);
}
}
}
inline void read() {
int a, b, c;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> a;
bad.push_back(a);
}
}
void dij() {
priority_queue < pii > pq;
for (int i : bad) {
pq.push({0, i});
dist[i] = 0;
}
while (pq.size()) {
int cur = pq.top().second;
int d = -pq.top().first;
pq.pop();
if (d > dist[cur]) {
continue;
}
for (pii i : g[cur]) {
int u = i.first;
int len = i.second;
if (dist[cur] + len < dist[u]) {
dist[u] = dist[cur] + len;
pq.push({-dist[u], u});
}
}
}
}
inline void solve() {
dij();
cin >> q;
querry.push_back({0, 0});
for (int i = 1; i <= q; i++) {
cin >> a >> b;
check(a, b);
querry.push_back({a, b});
int ans = dist[b];
if (dist[a] < dist[b]) {
ans = dist[a];
}
cout << ans << endl;
}
}
int main() {
int t;
//scanf("%d", &t);
t = 1;
//precalc();
while (t--) {
//purify();
read();
solve();
}
}