Submission #498224

#	Time	Username	Problem	Language	Result	Execution time	Memory
498224		sireanu_vlad	Evacuation plan (IZhO18_plan)	C++14	23 / 100	4089 ms	21284 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int oo = 2e9;
int n, m, k, q, s, t, d[100001], mind, maxd;
bool f[100001];
struct elem {int id, cost;};
vector<elem> g[100001];
struct comp
{
	bool operator()(int i, int j)
	{
		return d[i] > d[j];
	}
};
priority_queue<int, vector<int>, comp> pq;

void read()
{
	cin >> n >> m;
	for(int i = 0, x, y, c; i < m; ++i)
	{
		cin >> x >> y >> c;
		g[x].push_back({y, c});
		g[y].push_back({x, c});
	}

	for(int i = 1; i <= n; ++i)
		d[i] = oo;

	cin >> k;
	for(int i = 0, x; i < k; ++i)
	{
		cin >> x;
		pq.push(x);
		f[x] = 1;
		d[x] = 0;
	}

	cin >> q;
}

void dijkstra()
{
	int x;
	while(!pq.empty())
	{
		x = pq.top();
		f[x] = 0;
		pq.pop();
		for(auto i : g[x])
			if(d[x] + i.cost < d[i.id])
			{
				d[i.id] = d[x] + i.cost;
				if(f[i.id] == 0)
				{
					pq.push(i.id);
					f[i.id] = 1;
				}
			}
	}
}

void dfs(int nod)
{
	if(nod == t)
		maxd = max(maxd, min(mind, d[nod]));
	else
	{
		int aux = mind;
		mind = min(mind, d[nod]);
		f[nod] = 1;
		for(auto i : g[nod])
			if(!f[i.id])			
				dfs(i.id);
		mind = aux;
		f[nod] = 0;
	}
}

void solve()
{
	cin >> s >> t;
	if(d[s] == 0 || d[t] == 0)
	{
		cout << 0 << '\n';
		return;
	}
	for(auto i : g[s])
		if(i.id == t)
		{
			cout << min(d[s], d[t]) << '\n';
			return;
		}
	maxd = 0;
	mind = oo;
	dfs(s);
	cout << maxd << '\n';
}

int main()
{
	read();
	dijkstra();
	for(int i = 0; i < q; ++i)
		solve();
	return 0;
}

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