제출 #1052830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052830		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	357 ms	57152 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) (mask & (1<<j))
#define hoabanmatuy ios_base::sync_with_stdio(0);cin.tie(0);
#define ___HoaBanMaTuy___ int main () {
#define ___TheEnd___ return 0;}
const ll mod = 1e9 + 7;
const ll INF = 1e15;
const ll N = 1e5+10;
const ll M = 5e5+10;
ll n, m, k, Q;
ll d[N],ed[N],p[N],ans[N];
vector<pa> g[N];
priority_queue<pa, vector<pa>, greater<pa>> q;
set<ll> st[N];
void dextra()
{
	while (!q.empty())
	{
		ll u = q.top().se, i = q.top().fi;
		q.pop();
		if (d[u] != i) continue;
		for (auto e : g[u])
		{
			ll v = e.fi, w = e.se;
			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push({d[v], v});
			}
		}
	}
}
bool cmp(ll x,ll y)
{
	return d[x]>d[y];
}
ll findset(ll u)
{
	if(p[u]==0) return u;
	return (u == p[u] ? u : p[u] = findset(p[u]));
}
void ghep (ll u, ll v, ll w)
{
	u = findset(u);
	v = findset(v);
	if (u == v) return;
	if(st[v].size() > st[u].size()) swap(u,v);
	p[v] = u;
	for (auto e: st[v])
	{
		if(st[u].find(e)==st[u].end())
		{
			st[u].insert(e);
		}
		else
		{
			ans[e] = w;
			st[u].erase(e);
		}
	}
	st[v].clear();
}
___HoaBanMaTuy___

	hoabanmatuy
	memset(d, 0x3f, sizeof d);
	cin >> n >> m;
	FOR (i, 1, m)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	cin >> k;
	FOR (i, 1, k)
	{
		ll x;
		cin >> x;
		q.push({0, x});
		d[x] = 0;
	}
    
	cin>>Q;
	FOR (i, 1, Q)
	{
		ll u, v;
		cin >> u >> v;
		st[u].insert(i);
		st[v].insert(i);
	}
	dextra();
	FOR (i, 1, n) ed[i] = i;
	sort (ed + 1, ed + n + 1,cmp);
	FOR (i, 1, n)
	{
		ll u = ed[i];
		for (auto e : g[u])
		{
			ll v = e.fi;
			if(d[u]<=d[v])
			ghep(u, v, d[u]);
		}
	}
	FOR(i, 1, Q) cout << ans[i] << '\n'; 
___TheEnd___

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