Submission #99540

#	Time	Username	Problem	Language	Result	Execution time	Memory
99540		jhnah917	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	816 ms	45292 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> p;
vector<p> g[101010];
priority_queue<p> pq;
int dist1[101010], dist2[101010];
int visit[101010];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i=0; i<=N; i++) dist1[i] = dist2[i] = 1e9+7;
	for(int i=0; i<M; i++){
		int s = R[i][0], e = R[i][1], w = L[i];
		g[s].push_back({e, w});
		g[e].push_back({s, w});
	}
	for(int i=0; i<K; i++){
		dist1[P[i]] = dist2[P[i]] = 0;
		pq.push({0, P[i]});
	}
	
	while(!pq.empty()){
		int now = pq.top().second, cost = -pq.top().first;
		pq.pop();
		if(visit[now]) continue;
		visit[now] = 1;
		
		for(auto i : g[now]){
			int nxt = i.first, nxtCost = i.second;
			if(visit[nxt]) continue;
			//first
			if(dist1[nxt] > dist2[now] + nxtCost){
				dist2[nxt] = dist1[nxt];
				dist1[nxt] = dist2[now] + nxtCost;
				if(dist2[nxt] < 1e9+7) pq.push({-dist2[nxt], nxt});
			}
			//second
			else if(dist2[nxt] > dist2[now] + nxtCost){
				dist2[nxt] = dist2[now] + nxtCost;
				pq.push({-dist2[nxt], nxt});
			}
		}
	}
	
	return dist2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:26:30: warning: unused variable 'cost' [-Wunused-variable]
   int now = pq.top().second, cost = -pq.top().first;
                              ^~~~

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