Submission #443340

#	Time	Username	Problem	Language	Result	Execution time	Memory
443340		jesus_coconut	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	762 ms	90692 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using ll = long long;

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	vector<vector<pair<int, ll>>> adj(N);
	for (int i = 0; i < M; ++i) {
		adj[R[i][0]].emplace_back(R[i][1], L[i]);
		adj[R[i][1]].emplace_back(R[i][0], L[i]);
	}
	vector<array<ll, 2>> v(N, {LLONG_MAX/4, LLONG_MAX/4});
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
	for (int i = 0; i < K; ++i) {
		v[P[i]] = {0, 0};
		pq.emplace(0, P[i]);
	}

	vector<bool> bio(N);
	while (!pq.empty()) {
		auto [c, ver] = pq.top();
		pq.pop();
		if (bio[ver]) continue;
		bio[ver] = true;
		for (auto [u, w] : adj[ver]) if (!bio[u]) {
			if (c + w < v[u][0]) {
				v[u][1] = v[u][0];
				v[u][0] = c + w;
			} else if (c + w < v[u][1]) {
				v[u][1] = c + w;
			} else continue;
			pq.emplace(v[u][1], u);
		}
	}
	return v[0][1];
}
/*

int main() {
	*/
/*int R[][2] = {{0, 2}, {0, 3}, {3, 2}, {2, 1}, {0, 1}, {0, 4}, {3, 4}};
	int L[] = {4,3,2,10,100,7,9};
	int P[] = {1, 3};
	int N = 5;
	int M = 7;
	int K = 2;*//*


	int R[][2] = {{0, 1}, {0, 2}, {3, 2}, {2, 4}};
	int L[] = {2, 3, 1, 4};
	int P[] = {1, 3, 4};
	int N = 5;
	int M = 4;
	int K = 3;
	cout << travel_plan(N, M, R, L, K, P) << '\n';
}*/

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