| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1130384 | harut_13 | Evacuation plan (IZhO18_plan) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY cout<<"YES"<<endl
#define CN cout<<"NO"<<endl
#define ll long long
#define ciN cin
#define itn int
#define pshb push_back
#define sz size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl endl
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD 1000000007
using namespace std;
ll gcd(ll n1, ll n2)
{
if (n2 != 0)
return gcd(n2, n1 % n2);
else
return n1;
}
ll lcm(ll a, ll b) {
return a * b / (gcd(a, b));
}
ll pv(ll a, ll b) {
if (b == 0)return 1;
ll res = (pv(a, b / 2));
if (b % 2) {
return ((res) * (res) * (a));
}
else {
return (res) * (res);
}
}
void solve() {
int n, m; cin >> n >> m;
vector<vector<pll>> gp(n);
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
gp[--u].pshb({ --v,w });
gp[v].pshb({ u,w });
}
int k; cin >> k;
vec v(k);
for (int i = 0; i < k; i++) {
cin >> v[i];
v[i]--;
}
int q; cin >> q;
vector<pii> harc(q);
for (int i = 0; i < q; i++) {
cin >> harc[i].first;
cin >> harc[i].second;
harc[i].first--;
harc[i].second--;
}
vector<vecl> d(k, vecl(n,LLONG_MAX));
for (int i = 0; i < k; i++) {
int gag = v[i];
priority_queue<pll> pq;
d[i][gag] = 0;
pq.push({ 0,gag });
while (pq.sz) {
ll dist =-1*pq.top().first;
ll u = pq.top().second;
//cout << "??" << u << " " << dist << endl;
pq.pop();
if (dist != d[i][u])continue;
for (int j = 0; j < gp[u].sz; j++) {
int to = gp[u][j].first;
ll w = gp[u][j].second;
if (dist + w < d[i][to]) {
d[i][to] = dist + w;
pq.push({ -1 * d[i][to],to });
}
}
}
cout << endl;
}
vecl mn(n,1e18);
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
mn[j] = min(mn[j], d[i][j]);
}
cout << endl;
}
for (int i = 0; i < q; i++) {
cout << min(mn[harc[i].first], mn[harc[i].second]) << endl;
}
}
signed main() {
FASTIO
//int t; cin >> t;
//while (t--)
solve();
}