Submission #1039498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039498		sssamui	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	1 ms	4440 KiB

crocodile

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include "crocodile.h"
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 stt : prc)
	{
		min1[stt] = 0, min2[stt] = 0;
		djk.push({ 0, stt });
	}

	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: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11