Submission #206918

#	Time	Username	Problem	Language	Result	Execution time	Memory
206918		peuch	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1397 ms	49912 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
const int INF = 2000000000;

int n, m, k;
int marc[MAXN], isExit[MAXN], dist[MAXN], dist2[MAXN];
vector<int> v[MAXN], p[MAXN];

void dijkstra();

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n = N, m = M, k = K;
	for(int i = 0; i < m; i++){
		v[R[i][0]].push_back(R[i][1]);
		v[R[i][1]].push_back(R[i][0]);
		p[R[i][0]].push_back(L[i]);
		p[R[i][1]].push_back(L[i]);
	}
	for(int i = 0; i < k; i++)
		isExit[P[i]] = 1;
	dijkstra();
	return dist2[0];
}

void dijkstra(){
	set<pair<int, int> > out;
	for(int i = 0; i < n; i++){
		if(isExit[i]) dist[i] = 0, dist2[i] = 0;
		else dist[i] = INF, dist2[i] = INF;
		out.insert(make_pair(dist2[i], i));
	}
	while(!out.empty()){
		int cur = out.begin()->second;
		int curDist = out.begin()->first;
		marc[cur] = 1;
		out.erase(make_pair(curDist, cur));
		for(unsigned long i = 0; i < v[cur].size(); i++){
			int viz = v[cur][i];
			int vizDist = curDist + p[cur][i];
			if(marc[viz] == 1) continue;
			if(vizDist < dist[viz]){
				out.erase(make_pair(dist2[viz], viz));
				dist2[viz] = dist[viz];
				dist[viz] = vizDist;
				out.insert(make_pair(dist2[viz], viz));
			}
			else if(vizDist < dist2[viz]){
				out.erase(make_pair(dist2[viz], viz));
				dist2[viz] = vizDist;
				out.insert(make_pair(dist2[viz], viz));
			}
		}
	}
}

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