Submission #583551

#	Time	Username	Problem	Language	Result	Execution time	Memory
583551		benson1029	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	451 ms	48564 KiB

crocodile

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

vector< pair<int,int> > edg[100005];
long long dis[100005], dis1[100005], dis2[100005];
priority_queue< pair<long long, int> > pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i=0; i<N; i++) {
		dis1[i] = dis2[i] = 1e17;
		dis[i] = 2e17;
	}
	for(int i=0; i<M; i++) {
		edg[R[i][0]].push_back({R[i][1], L[i]});
		edg[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i=0; i<K; i++) {
		dis[P[i]] = dis1[P[i]] = dis2[P[i]] = 0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()) {
		int curr = pq.top().second;
		if(dis[curr] != -pq.top().first) {
			pq.pop();
			continue;
		}
		if(curr==0) return dis[curr];
		pq.pop();
		for(auto i:edg[curr]) {
			if(dis[curr]+i.second < dis1[i.first]) {
				dis2[i.first] = dis1[i.first];
				dis1[i.first] = dis[curr]+i.second;
			} else if(dis[curr]+i.second < dis2[i.first]) {
				dis2[i.first] = dis[curr]+i.second;
			} else continue;
			if(dis2[i.first] < 1e17 && dis2[i.first] < dis[i.first]) {
				dis[i.first] = dis2[i.first];
				pq.push({-dis[i.first], i.first});
			}
		}
	}
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

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