Submission #341387

#	Time	Username	Problem	Language	Result	Execution time	Memory
341387		_ani	Evacuation plan (IZhO18_plan)	C++17	23 / 100	1010 ms	28128 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;
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'00 + 69;
	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 });
		if (a > b)swap(a, b);
	}
	int k;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		d[x] = 0;
		q.push({ 0, x });
	}
	int Q;
	cin >> Q;
	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 });
			}
	}
	if (n > 1000 || Q > 1)
	{
		while (Q--)
		{
			int s, t;
			cin >> s >> t;
			cout << min(d[s], d[t]) << '\n';
		}
		return 0;
	}
	while (Q--)
	{
		int s, t;
		cin >> s >> t;
		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: 13 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46