Submission #220872

#	Time	Username	Problem	Language	Result	Execution time	Memory
220872		spdskatr	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	690 ms	64396 KiB

crocodile

#include "crocodile.h"
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <functional>
#include <cstdio>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, int> entry;
typedef long long ll;

ll da[100005], db[100005];
int done[100005];
vector<pii> graph[100005];
priority_queue<entry, vector<entry>, greater<entry>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0; i < M; i++) {
		graph[R[i][0]].push_back({ R[i][1], L[i] });
		graph[R[i][1]].push_back({ R[i][0], L[i] });
	}
	for (int i = 0; i < N; i++) da[i] = db[i] = -1;
	for (int i = 0; i < K; i++) {
		da[P[i]] = db[P[i]] = 0;
		pq.push({ db[P[i]], P[i] });
	}
	while (!pq.empty()) {
		entry e = pq.top(); pq.pop();
		int u = e.se;
		if (done[e.se]) continue;
		done[e.se] = 1;
		for (pii p : graph[u]) {
			int v = p.fi, w = p.se;
			if (!done[v]) {
				if (da[v] == -1 || da[v] >= db[u] + w) {
					db[v] = da[v];
					da[v] = db[u] + w;
					if (db[v] != -1) pq.push({ db[v], v });
				} else if (db[v] == -1 || db[v] > db[u] + w) {
					db[v] = db[u] + w;
					pq.push({ db[v], v });
				}
			}
		}
	}
	return (int)db[0];
}

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