Submission #112539

#	Time	Username	Problem	Language	Result	Execution time	Memory
112539		nxteru	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	850 ms	72840 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll f[100005],s[100005];
vector<P>g[100005];
int travel_plan(int n, int m, int R[][2], int L[], int k, int T[]){
	for(int i=0;i<m;i++){
		ll a=R[i][0],b=R[i][1],c=L[i];
		g[a].PB(P(b,c));
		g[b].PB(P(a,c));
	}
	for(int i=0;i<n;i++)f[i]=INF,s[i]=INF;
	priority_queue<P,vector<P>,greater<P>>dik;
	for(int i=0;i<k;i++){
		ll v=T[i];
		f[v]=0;
		s[v]=0;
		dik.push(P(0,v));
	}
	while(!dik.empty()){
		ll c=dik.top().F,v=dik.top().S;
		dik.pop();
		if(s[v]<c)continue;
		for(int i=0;i<g[v].size();i++){
			ll u=g[v][i].F,p=c+g[v][i].S;
			if(f[u]>p)swap(f[u],p);
			if(s[u]>p){
				s[u]=p;
				dik.push(P(p,u));
			}
		}
	}
	return s[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[v].size();i++){
               ~^~~~~~~~~~~~

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