답안 #210553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210553	2020-03-17T17:02:00 Z	faremy	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	1247 ms	101564 KB

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.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2680 KB	Output is correct
2	Correct	6 ms	2680 KB	Output is correct
3	Correct	8 ms	2680 KB	Output is correct
4	Correct	8 ms	2808 KB	Output is correct
5	Correct	7 ms	2808 KB	Output is correct
6	Correct	7 ms	2812 KB	Output is correct
7	Correct	7 ms	2808 KB	Output is correct
8	Correct	7 ms	2808 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2680 KB	Output is correct
2	Correct	6 ms	2680 KB	Output is correct
3	Correct	8 ms	2680 KB	Output is correct
4	Correct	8 ms	2808 KB	Output is correct
5	Correct	7 ms	2808 KB	Output is correct
6	Correct	7 ms	2812 KB	Output is correct
7	Correct	7 ms	2808 KB	Output is correct
8	Correct	7 ms	2808 KB	Output is correct
9	Correct	9 ms	3448 KB	Output is correct
10	Correct	6 ms	2680 KB	Output is correct
11	Correct	7 ms	2936 KB	Output is correct
12	Correct	13 ms	3936 KB	Output is correct
13	Correct	11 ms	4096 KB	Output is correct
14	Correct	6 ms	2684 KB	Output is correct
15	Correct	7 ms	2808 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2680 KB	Output is correct
2	Correct	6 ms	2680 KB	Output is correct
3	Correct	8 ms	2680 KB	Output is correct
4	Correct	8 ms	2808 KB	Output is correct
5	Correct	7 ms	2808 KB	Output is correct
6	Correct	7 ms	2812 KB	Output is correct
7	Correct	7 ms	2808 KB	Output is correct
8	Correct	7 ms	2808 KB	Output is correct
9	Correct	9 ms	3448 KB	Output is correct
10	Correct	6 ms	2680 KB	Output is correct
11	Correct	7 ms	2936 KB	Output is correct
12	Correct	13 ms	3936 KB	Output is correct
13	Correct	11 ms	4096 KB	Output is correct
14	Correct	6 ms	2684 KB	Output is correct
15	Correct	7 ms	2808 KB	Output is correct
16	Correct	1127 ms	97216 KB	Output is correct
17	Correct	111 ms	14456 KB	Output is correct
18	Correct	150 ms	16632 KB	Output is correct
19	Correct	1247 ms	101564 KB	Output is correct
20	Correct	703 ms	87508 KB	Output is correct
21	Correct	60 ms	8312 KB	Output is correct
22	Correct	632 ms	51056 KB	Output is correct