Submission #6995

#	Time	Username	Problem	Language	Result	Execution time	Memory
6995		gs13068	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	1252 ms	173292 KiB

crocodile

#include<vector>
#include<queue>

std::vector<std::pair<int,int> > G[100000];
std::priority_queue<std::pair<int,int> > PQ;
std::pair<int,int> P;
int D[100000];

int travel_plan(int N,int M,int R[][2],int L[],int K,int X[])
{
    int i;
    for(i=0;i<N;i++)
	{
		G[i].clear();
		D[i]=-1;
	}
    for(i=0;i<M;i++)
	{
		G[R[i][0]].push_back(std::make_pair(R[i][1],L[i]));
		G[R[i][1]].push_back(std::make_pair(R[i][0],L[i]));
	}
	for(i=0;i<K;i++)
	{
        D[X[i]]=-2;
		PQ.push(std::make_pair(0,X[i]));
	}
    while(!PQ.empty())
	{
		P=PQ.top();
		PQ.pop();
		if(D[P.second]>=0)continue;
		if(D[P.second]==-1)
		{
			D[P.second]=-2;
			continue;
		}
		D[P.second]=-P.first;
        for(i=0;i<G[P.second].size();i++)PQ.push(std::make_pair(P.first-G[P.second][i].second,G[P.second][i].first));
	}
	return D[0];
}

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