Submission #883714

#	Time	Username	Problem	Language	Result	Execution time	Memory
883714		OAleksa	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4038 ms	83816 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int maxn = 1e5 + 69;
set<pair<int, int>> g[maxn];
int n, m, k, cnt[maxn], d[maxn], q, mn[maxn];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
	//cin >> tt;
  while (tt--) {
   	cin >> n >> m;
   	for (int i = 1;i <= m;i++) {
   		int a, b, w;
   		cin >> a >> b >> w;
   		g[a].insert({b, w});
   		g[b].insert({a, w});
   	}
   	cin >> k;
   	for (int i = 1;i <= k;i++) {
   		int x;
   		cin >> x;
   		cnt[x] = 1;
   	}
   	cin >> q;
   	priority_queue<pair<int, int>> pq;	
   	for (int i = 1;i <= n;i++) {
   		d[i] = 1e18;
   		if (cnt[i]) {
   			pq.push({0, i});
   			d[i] = 0;
   		}
   	}
   	while (!pq.empty()) {
   		auto v = pq.top().s;
   		pq.pop();
   		for (auto u : g[v]) {
   			if (d[u.f] <= d[v] + u.s)
   				continue;
   			d[u.f] = d[v] + u.s;
   			pq.push({-d[u.f], u.f});
   		}
   	}
   	for (int i = 1;i <= q;i++) {
   		int s, t;
   		cin >> s >> t;
   		auto u = *g[s].lower_bound({t, -1});
   		if (u.f == t)
   			cout << min(d[s], d[t]) << '\n';
   		else {
   			for (int i = 1;i <= n;i++)
   				mn[i] = 0;
   			mn[s] = d[s];
   			queue<int> q;
   			q.push(s);
   			while (!q.empty()) {
   				auto v = q.front();
   				q.pop();
   				for (auto u : g[v]) {
   					auto vr = min(mn[v], d[u.f]);
   					if (vr <= mn[u.f])
   						continue;
   					mn[u.f] = vr;
   					q.push(u.f);
   				}
   			}
   			cout << mn[t] << '\n';
   		}
   	}
	}
	return 0;
}

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