Submission #341368

#	Time	Username	Problem	Language	Result	Execution time	Memory
341368		_ani	Evacuation plan (IZhO18_plan)	C++17	22 / 100	1784 ms	61644 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
vector<pair<int, int>> g[100002];
priority_queue<pair<int, int>> q;
map<pair<int, int>, int> f;
int d[100002], p[100002];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		d[i] = 1'000'000;
	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		g[a].push_back({ b,w });
		g[b].push_back({ a,w });
		f[{ min(a, b), max(a, b) }] = 1;
	}
	int k;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		d[x] = 0;
		q.push({ 0, x });
	}
	while (!q.empty()) {
		int sz = -q.top().first;
		int v = q.top().second;
		q.pop();
		if (sz > d[v])continue;
		for (auto to : g[v])
			if (to.second + d[v] < d[to.first])
			{
				d[to.first] = to.second + d[v];
				q.push({ -d[to.first], to.first });
			}
	}
	int Q;
	cin >> Q;
	while (Q--)
	{
		int s, t;
		cin >> s >> t;
		if (s > t)swap(s, t);
		if (f[{ s, t }])
		{
			cout << min(d[s], d[t]) << '\n';
			continue;
		}
		for (int i = 1; i <= n; i++)
			p[i] = -1'000'000;
		p[s] = d[s];
		q.push({ d[s], s });
		while (!q.empty()) {
			int sz = q.top().first;
			int v = q.top().second;
			q.pop();
			if (sz < p[v])continue;
			for (auto to : g[v])
				if (min(d[to.first], p[v]) > p[to.first])
				{
					p[to.first] = min(d[to.first], p[v]);
					q.push({ p[to.first], to.first });
				}
		}
		cout << p[t] << '\n';
	}
	return 0;
}

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