제출 #140662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140662		eohomegrownapps	악어의 지하 도시 (IOI11_crocodile)	C++14	89 / 100	828 ms	77092 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18;
vector<vector<pair<ll,ll> > > adjlist;
vector<ll> safe;
vector<ll> shortest;
vector<ll> secshortest;
ll n;

void dijkstra(){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	for (ll i : safe){
		pq.push(make_pair(0,i));
	}
	while (pq.size()>0){
		auto f = pq.top();
		pq.pop();
		if (f.first>secshortest[f.second]){
			continue;
		}
		//cout<<"process "<<f.second<<endl;
		for (auto i : adjlist[f.second]){
			if (secshortest[i.second]>secshortest[f.second]+i.first){
				if (secshortest[f.second]+i.first<=shortest[i.second]){
					secshortest[i.second]=shortest[i.second];
					shortest[i.second]=secshortest[f.second]+i.first;
				} else {
					secshortest[i.second]=secshortest[f.second]+i.first;
				}
				pq.push(make_pair(secshortest[i.second],i.second));
			}
		}
		/*for (ll i : shortest){
			cout<<(i==INF?-1:i)<<" ";
		}cout<<endl;
		for (ll i : secshortest){
			cout<<(i==INF?-1:i)<<" ";
		}cout<<endl;
		cout<<"==="<<endl;*/
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N;
	adjlist.resize(n);
	safe.resize(K);
	shortest.resize(n,INF);
	secshortest.resize(n,INF);
	for (int i = 0; i<M; i++){
		adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
		adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
	}
	for (int i = 0; i<K; i++){
		safe[i]=P[i];
		shortest[P[i]]=0;
		secshortest[P[i]]=0;
	}
	dijkstra();
	return secshortest[0];
}

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