Submission #499122

#	Time	Username	Problem	Language	Result	Execution time	Memory
499122		sireanu_vlad	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4080 ms	26580 KiB

plan

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

const int oo = 2e9;
int n, m, k, q, s, t, d[100001], mind, ans, r[100001], tt[100001];
bool f[100001];
struct elem {int id, cost;};
vector<elem> g[100001];
vector<int> g2[100001];
struct comp
{
	bool operator()(int i, int j)
	{
		return d[i] > d[j];
	}
};
priority_queue<int, vector<int>, comp> pq;
struct edge {int x, y;};
vector<edge> e; 
bool comp2(const edge& a, const edge& b)
{
	return min(d[a.x], d[a.y]) > min(d[b.x], d[b.y]);
}

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});
		e.push_back({x, y});
	}

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

	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;
				}
			}
	}
}

int root(int x)
{
	if(tt[x] == x)
		return x;
	return root(tt[x]);
}

void U(int x, int y)
{
	if(r[x] < r[y]) tt[x] = y;
	else if(r[x] > r[y]) tt[y] = x;
	else tt[y] = x, r[x]++;
}

void kruskal()
{
	int nr = 0, rx, ry;
	for(auto i : e)
	{
		rx = root(i.x);
		ry = root(i.y);
		if(rx != ry)
		{
			U(rx, ry);
			g2[i.x].push_back(i.y);
			g2[i.y].push_back(i.x);
			if(++nr == n-1) break;
		}
	}
}

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

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;
		}
	mind = d[s];
	dfs(s);
	cout << ans << '\n';
}

int main()
{
	read();
	dijkstra();
	sort(e.begin(), e.end(), comp2);
	kruskal();
	for(int i = 0; i < q; ++i)
		solve();
	return 0;
}

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