Submission #222907

#	Time	Username	Problem	Language	Result	Execution time	Memory
222907		MODDI	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	754 ms	72352 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<pair<int,int> > G[100010];
vector<int> exits;
int dijkstra()
{
	int vis[n];
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int> > pq;
	for(int i=0;i<exits.size();i++)
	{
		int exit = exits[i];
		pq.push(make_pair(0,exit));
		vis[exit] = 1;
	}
	while(!pq.empty())
	{
		pair<int,int> state = pq.top(); pq.pop();
		int path = -state.first;
		int city = state.second;
		//cout<<"at city "<<city<<" with path "<<path<<endl;
		if(vis[city] == 0){
			vis[city] = 1;
			continue;
		}
		if(vis[city] == 2)
			continue;
			
		if(city == 0)
			return path;
			
		vis[city] = 2;
		vector<pair<int,int> > can_go = G[city];
		for(int i=0;i<can_go.size();i++)
		{
			int next = can_go[i].first;
			int len = can_go[i].second;
			len += path;
			pq.push(make_pair(-len,next));
		}
		
	}
}
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++){
		int a, b, c;
		a = R[i][0], b = R[i][1], c = L[i];
		G[a].push_back(make_pair(b,c));
		G[b].push_back(make_pair(a,c));
	}
	for(int i = 0; i < k; i++){
		int exit = P[i];
		exits.push_back(exit);
	}
	return dijkstra();
}
/*int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i =0;i<m;i++)
	{
		int a, b, c;
		cin>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
		G[b].push_back(make_pair(a,c));
	}
	for(int i =0;i<k;i++)
	{
		int exit;
		cin>>exit;
		exits.push_back(exit);
	}
	cout<<dijkstra()<<endl;
	return 0;
} */

Compilation message (stderr)

crocodile.cpp: In function 'int dijkstra()':
crocodile.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<exits.size();i++)
              ~^~~~~~~~~~~~~
crocodile.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<can_go.size();i++)
               ~^~~~~~~~~~~~~~
crocodile.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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