Submission #571446

#	Time	Username	Problem	Language	Result	Execution time	Memory
571446		choigameautohackrb	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4072 ms	55756 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll N = 1e6 + 5;
const ll inf = 1e9;

ll n, m, k, qq, d[N];
vector <pair<ll, ll>> g[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (ll i = 1; i <= m; ++ i) {
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for (int i = 1; i <= n; ++ i) d[i] = inf;
	cin >> k;
	queue <int> Que;
	for (int i = 1; i <= k; ++ i) {
		ll x; cin >> x;
		d[x] = 0;
		Que.push(x);
	}
	while (Que.size()) {
		ll v = Que.front();
		Que.pop();
		for (auto [to, w] : g[v]) {
			if (d[to] > d[v] + w) {
		    	d[to] = d[v] + w;
				Que.push(to);
			}
		}
	}
	cin >> qq;
	while (qq --) {
		ll a, b;
		cin >> a >> b;
		vector <ll> res(n + 5, 0);
		Que.push(a);
		res[a] = d[a];
		while (Que.size()) {
			ll v = Que.front();
			Que.pop();
			for (auto [to, w] : g[v]) {
				if (res[to] < min(res[v], d[to])) {
					res[to] = min(res[v], d[to]);
					Que.push(to);
				}
			}
		}
		cout << res[b] << '\n';
	}
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46