Submission #1039501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039501		sssamui	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	277 ms	61736 KiB

crocodile

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	vector<int> min1(N, 1e9 + 1), min2(N, 1e9 + 1);
	vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>(0));
	for (int i = 0; i < M; i++)
	{
		adj[R[i][0]].push_back({ L[i], R[i][1] }), adj[R[i][1]].push_back({ L[i], R[i][0] });
	}

	priority_queue<pair<int, int>> djk;
	vector<bool> prc(N, false);
	for (int i = 0; i < K; i++)
	{
		min1[P[i]] = 0, min2[P[i]] = 0;
		djk.push({ 0, P[i]});
	}

	while (!djk.empty())
	{
		int d = -djk.top().first, node = djk.top().second;
		djk.pop();
		if ((d == min2[node]) && !prc[node])
		{
			prc[node] = true;
			for (pair<int, int> nxt : adj[node])
			{
				if (d + nxt.first < min1[nxt.second])
				{
					min2[nxt.second] = min1[nxt.second];
					min1[nxt.second] = d + nxt.first;
					djk.push({ -d - nxt.first, nxt.second });
				}

				else if (d + nxt.first < min2[nxt.second])
				{
					min2[nxt.second] = d + nxt.first;
					djk.push({ -d - nxt.first, nxt.second });
				}
			}
		}
	}

	return min2[0];
}

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