Submission #1268490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268490		bajtozaur	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	0 ms	324 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

	vector<pair<int, int>> G[N+5];
	//<to, cost>
	
	vector<int> block(N+5, -1);
	vector<bool> odw(N+5, 0);

	priority_queue<pair<long long, pair<int, int>>> PQ;
	//<-cost>,<from, to>

	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]});
	}
	
	
	/////////
	
	for(int i=0; i<K; i++){
		int e = P[i];
		odw[e] = 1;
		for(int j=0; j<G[e].size(); j++){
			PQ.push({-G[e][j].second, {e, G[e][j].first}});
			//cout << G[e][j].second << ' ' << e << ' ' << G[e][j].first << '\n';
		}
	}
	
	
	while(!PQ.empty()){
		
		long long cost = -PQ.top().first;
		int from = PQ.top().second.first;
		int to = PQ.top().second.second;
		
		//cout << "go " << cost << ' ' << from << ' ' << to << '\n';
		
		if(block[to] == -1){
			block[to] = from;
		}else{
			if(to == 0){
				return cost;
			}
			if(!odw[to]){
				for(int i=0; i<G[to].size(); i++){
					pair<int, int> s = G[to][i];
					if(s.first != from && s.first != block[to]){
						PQ.push({-(cost+s.second), {to, s.first}});
						//cout << "add " << cost+s.second << ' ' << to << ' ' << s.first << '\n';
					}
				}
			}
		}
		
		PQ.pop();
	}
	
	
	
	return 0;
}

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