답안 #263342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
263342	2020-08-13T15:50:26 Z	Berted	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	697 ms	61680 KB

crocodile

#include "crocodile.h"
#include <queue>
#include <vector>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define snd second
#define vpi vector<pii>

using namespace std;

const int INF = 2e9;

priority_queue<pii, vector<pii>, greater<pii>> pq;
int dst[100001], mn[100001][2];
vpi adj[100001];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < N; i++)
	{
		dst[i] = mn[i][0] = mn[i][1] = INF;
	}
	for (int i = 0; i < M; i++)
	{
		int u = R[i][0], v = R[i][1];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	for (int i = 0; i < K; i++)
	{
		dst[P[i]] = mn[P[i]][0] = mn[P[i]][1] = 0;
		pq.emplace(0, P[i]);
	}
	while (pq.size())
	{
		int u = pq.top().snd; int d = pq.top().fst; pq.pop();
		if (d == dst[u])
		{
			if (u == 0) break;
			for (auto v : adj[u])
			{
				if (d + v.snd < mn[v.fst][0])
				{
					mn[v.fst][1] = mn[v.fst][0];
					mn[v.fst][0] = d + v.snd;
				}
				else if (d + v.snd < mn[v.fst][1])
				{
					mn[v.fst][1] = d + v.snd;
				}
				if (mn[v.fst][1] < dst[v.fst]) 
				{
					dst[v.fst] = mn[v.fst][1];
					pq.push({mn[v.fst][1], v.fst});
				}
			}
		}
	}
	return dst[0];
}

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2688 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	4 ms	2944 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	3 ms	2816 KB	Output is correct
12	Correct	6 ms	3200 KB	Output is correct
13	Correct	6 ms	3200 KB	Output is correct
14	Correct	2 ms	2688 KB	Output is correct
15	Correct	3 ms	2816 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2688 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	4 ms	2944 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	3 ms	2816 KB	Output is correct
12	Correct	6 ms	3200 KB	Output is correct
13	Correct	6 ms	3200 KB	Output is correct
14	Correct	2 ms	2688 KB	Output is correct
15	Correct	3 ms	2816 KB	Output is correct
16	Correct	607 ms	57328 KB	Output is correct
17	Correct	96 ms	14304 KB	Output is correct
18	Correct	108 ms	15608 KB	Output is correct
19	Correct	697 ms	61680 KB	Output is correct
20	Correct	369 ms	49656 KB	Output is correct
21	Correct	46 ms	7928 KB	Output is correct
22	Correct	382 ms	46136 KB	Output is correct