Submission #367691

#	Time	Username	Problem	Language	Result	Execution time	Memory
367691		8e7	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	615 ms	61160 KiB

crocodile

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include "crocodile.h"
#define maxn 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
using namespace std;
const int inf = 1<<30;
int mind[maxn][2];
vector<pii> adj[maxn];

inline bool cmp(pii a, pii b) {
	return a.ss > b.ss;
}
priority_queue<pii, vector<pii>, bool (*) (pii, pii) > pq(cmp);
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0;i < M;i++) {
		adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	for (int i = 0;i < N;i++) mind[i][0] = mind[i][1] = inf;
	for (int i = 0;i < K;i++) {
		mind[P[i]][0] = mind[P[i]][1] = 0;
		pq.push(make_pair(P[i], 0));
	}

	while (pq.size()) {
		int cur = pq.top().ff, dis = pq.top().ss;
		pq.pop();
		if (dis != mind[cur][1]) continue;
		for (auto v:adj[cur]) {
			int nd = dis + v.ss, orig = mind[v.ff][1];
			if (nd <= mind[v.ff][0]) {
				mind[v.ff][1] = mind[v.ff][0];
				mind[v.ff][0] = nd;
			} else if (nd < mind[v.ff][1]) {
				mind[v.ff][1] = nd;
			}
			if (mind[v.ff][1] < orig) {
				pq.push(make_pair(v.ff, mind[v.ff][1]));
			}
		}
	}
	return mind[0][1];
}

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