Submission #607687

#	Time	Username	Problem	Language	Result	Execution time	Memory
607687		Temmie	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	479 ms	87620 KiB

crocodile

#include <bits/stdc++.h>

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	std::vector <std::vector <std::pair <int, int>>> g(n);
	for (int i = 0; i < m; i++) {
		g[r[i][0]].emplace_back(r[i][1], l[i]);
		g[r[i][1]].emplace_back(r[i][0], l[i]);
	}
	std::vector <int> cnt(n, 0);
	std::priority_queue <std::pair <long long, int>> pq;
	for (int i = 0; i < k; i++) {
		cnt[p[i]] = 1;
		pq.push({ 0, p[i] });
	}
	while (pq.size()) {
		long long w = -pq.top().first;
		int v = pq.top().second;
		pq.pop();
		if (cnt[v] >= 2) {
			continue;
		}
		cnt[v]++;
		if (cnt[v] == 1) {
			continue;
		}
		assert(cnt[v] == 2);
		if (!v) {
			return w;
		}
		for (auto q : g[v]) {
			pq.push({ -w - q.second, q.first });
		}
	}
	assert(false);
	return 0;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11