제출 #906577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906577		Mathias	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	6492 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
using namespace std;
const ll INF = 1e18+7;
const int MAXN = 1e5+7;
vector<pair<int,int> > g[MAXN];
queue<pair<ll,int> > kp;
ll d[MAXN][2];	bool visited[MAXN];
int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]){
	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<N;i++) d[i][0]=d[i][1]=INF;
	for(int i=0;i<K;i++){
		d[P[i]][0]=d[P[i]][1]=0;
		kp.push({0,P[i]});
	}
	//for(int i=0;i<N;i++) cout<<i<<' '<<d[i][0]<<' '<<d[i][1]<<'\n';
	while(!kp.empty()){
		int x=kp.front().second;
		kp.pop();
		if(visited[x]) continue;
		visited[x]=1;
		//cout<<"x="<<x<<'\n';
		for(auto s:g[x]){
			if(d[s.first][0]>d[s.first][1]) swap(d[s.first][0],d[s.first][1]);
			if(max(d[x][0],d[x][1])+s.second<d[s.first][1]){
				d[s.first][1]=min(INF, max(d[x][0],d[x][1])+s.second);
				if(max(d[s.first][0],d[s.first][1])<INF) kp.push({-max(d[s.first][1], d[s.first][0]),s.first});
			}
		}
	}
	return (int)max(d[0][0],d[0][1]);
}/*
int main(){
	int n,m,k;
	int R[100][2], L[100], P[100];
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>R[i-1][0]>>R[i-1][1]>>L[i-1];
	cin>>k;
	for(int i=0;i<k;i++) cin>>P[i];
	cout<<travel_plan(n,m,R,L,k,P)<<'\n';
}*/

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