Submission #210553

#	Time	Username	Problem	Language	Result	Execution time	Memory
210553		faremy	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1247 ms	101564 KiB

crocodile

#include "crocodile.h"

#include <vector>
#include <queue>


struct Edge
{
	Edge(int v, long long w) : dest(v), weight(w) {}
	int dest;
	long long weight;

	bool operator <(const Edge &other) const
	{
		return (other.weight < weight);
	}
};

const int MAXN = 1e5;
const long long INFTY = 1e18;

std::vector<Edge> graph[MAXN];
std::priority_queue<Edge> paths;
long long shortest[MAXN][2];


void dijkstra()
{
	while (!paths.empty())
	{
		int node = paths.top().dest;
		long long dist = paths.top().weight;
		paths.pop();

		if (shortest[node][0] == INFTY)
			shortest[node][0] = dist;
		else if (shortest[node][1] == INFTY)
		{
			shortest[node][1] = dist;
			for (Edge &edge : graph[node])
				paths.emplace(edge.dest, dist + edge.weight);
		}
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	std::fill_n((long long *)shortest, N * 2, INFTY);
	for (int iEdge = 0; iEdge < M; iEdge++)
	{
		graph[R[iEdge][0]].emplace_back(R[iEdge][1], L[iEdge]);
		graph[R[iEdge][1]].emplace_back(R[iEdge][0], L[iEdge]);
	}

	for (int iExit = 0; iExit < K; iExit++)
	{
		shortest[P[iExit]][0] = 0;
		paths.emplace(P[iExit], 0);
	}

	dijkstra();
	return shortest[0][1];
}

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