Submission #1024932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024932		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	262 ms	29800 KiB

plan

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> adjl(n+1);
	for (int i=0; i<m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adjl[u].emplace_back(v, w);
		adjl[v].emplace_back(u, w);
	}

	int k;
	cin >> k;
	vector<int> npp(k);
	for (int i=0; i<k; i++) cin >> npp[i];

	const int inf = 1e9+3;
	vector<int> dist(n+1, inf);
	vector<bool> vis(n+1, false);
	priority_queue<pair<int, int>> pq;
	for (int i=0; i<k; i++) dist[npp[i]] = 0, pq.emplace(-dist[npp[i]], npp[i]);
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto &[v, w] : adjl[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.emplace(-dist[v], v);
			}
		}
	}

	vector<int> par(n+1), sez(n+1), ud(n+1, -1);
	for (int i=1; i<=n; i++) par[i] = i, sez[i] = 1;
	auto find = [&](int u) -> int {
		while (u != par[u]) u = par[u];
		return u;
	};
	auto unite = [&](int u, int v, int d) -> void {
		u = find(u); v = find(v);
		if (u == v) return;
		if (sez[u] > sez[v]) swap(u, v);
		par[u] = v; sez[v] += sez[u]; ud[u] = d;
	};
	auto mnd = [&](int u, int v) -> int {
		int ret = min(dist[u], dist[v]);
		while (u != v) {
			if (ud[u] <= ud[v]) swap(u, v);
			ret = min(ret, ud[u]);
			u = par[u];
		}
		return ret;
	};

	vector<int> su(n);
	for (int i=0; i<n; i++) su[i] = i+1;
	sort(su.begin(), su.end(), [&](int u, int v) {
		return dist[u] > dist[v];
	});
	for (int u : su) {
		for (auto &[v, _] : adjl[u]) {
			if (dist[v] > dist[u] || (dist[v] == dist[u] && u < v)) {
				unite(u, v, dist[u]);
			}
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << mnd(u, v) << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tcs = 1;
	// cin >> tcs;
	while (tcs--) {
		solve();
	}
	return 0;
}

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