제출 #1268499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268499		bajtozaur	악어의 지하 도시 (IOI11_crocodile)	C++20	89 / 100	2096 ms	104152 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(block[to] != from){
			if(to == 0){
				return cost;
			}
			odw[to] = 1;
			for(int i=0; i<G[to].size(); i++){
				pair<int, int> s = G[to][i];
				if(!odw[s.first]){
					PQ.push({-(cost+s.second), {to, s.first}});
					//cout << "add " << cost+s.second << ' ' << to << ' ' << s.first << '\n';
				}
			}
		}
		
		PQ.pop();
	}
	
	
	
	return 0;
}

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