Submission #896530

#	Time	Username	Problem	Language	Result	Execution time	Memory
896530		LCJLY	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	360 ms	49608 KiB

crocodile

#include "crocodile.h"
//
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
//#define int long long
vector<pii>adj[100005];

int travel_plan(int n, int m, int r[][2], int w[], int k, int p[]){
	for(int x=0;x<m;x++){
		adj[r[x][0]].push_back({r[x][1],w[x]});
		adj[r[x][1]].push_back({r[x][0],w[x]});
	}
	
	pii dist[n+5];
	//memset(dist,-1,sizeof(dist));
	for(int x=0;x<n;x++){
		dist[x]={INT_MAX,INT_MAX};
	}
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int x=0;x<k;x++){
		dist[p[x]]={0,0};
		pq.push({0,p[x]});
	}
	
	bool visited[n+5];
	memset(visited,0,sizeof(visited));
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int x=cur.second;
		int d=cur.first;
		if(dist[x].second!=d||visited[x]) continue;
		visited[x]=true;
		
		for(auto it:adj[x]){
			int nx=it.first;
			int nd=d+it.second;
			if(nd<=dist[nx].first){
				dist[nx].second=dist[nx].first;
				dist[nx].first=nd;
				pq.push({nd,nx});
			}
			else if(nd<dist[nx].second){
				dist[nx].second=nd;
				pq.push({nd,nx});
			}
		}
	}
	
	if(dist[0].second!=-1){
		return dist[0].second;
	}
	else return -1;
}

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