oj.uz

Submission #1039498

# Submission time Handle Problem Language Result Execution time Memory
1039498 2024-07-31T01:21:08 Z sssamui Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 4440 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -