Submission #600297

#	Time	Username	Problem	Language	Result	Execution time	Memory
600297		shezitt	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	468 ms	75140 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define dbg(x) cout << #x << ": " << x << endl;
#define raya cout << "===========================" << endl;
typedef long long ll;

using namespace std;

const ll INF = 1e18;
const int N = 1e5+5;
int n, m;

int vis[N];
vector<pair<int,int>> g[N];

int travel_plan(int nn, int mm, int R[][2], int L[], int K, int P[]){
	n = nn;
	m = mm;
	for(int i=0; i<m; ++i){
		g[R[i][0]].push_back({R[i][1], L[i]});
		g[R[i][1]].push_back({R[i][0], L[i]});
	}
	
	priority_queue<pair<ll,int>> pq;
	for(int i=0; i<K; ++i){
		pq.push({0, P[i]});
		vis[P[i]] = 1;
	}
	while(!pq.empty()){
		auto w = -pq.top().first; auto u = pq.top().second;
		pq.pop();
		if(!vis[u]){
			vis[u] = 1;
			continue;
		}
		if(vis[u] == 2){
			continue;
		}
		if(u == 0){
			return w;
		}
		vis[u] = 2;
		for(auto v : g[u]){
			if(vis[v.first] == 2){
				continue;
			}
			pq.push({-(w+v.second), v.first});
		}
		
	}
	assert(0);
	return -1;
}

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