제출 #1293550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293550		settop	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	262 ms	45084 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"

using namespace std;

#define pb push_back
#define fall(i,a,b) for(int i=a;i<=b;i++)
const int MAXN=1e5+10;

typedef pair<int,int> pii;

int dp[MAXN],dp2[MAXN];
vector<pii> g[MAXN];
bool ex[MAXN],vis[MAXN];

int djk(int n){
	priority_queue<pii,vector<pii>,greater<pii>> pq;

	fall(i,0,n-1){
		if(ex[i]) pq.push({0,i});
		else dp[i]=dp2[i]=2e9;
	}

	while(!pq.empty()){
		auto [d,x]=pq.top(); pq.pop();

		if(d!=dp2[x] || vis[x]) continue;

		vis[x]=1;

		for(auto [u,j]:g[x]){
			if(dp[u]>dp2[x]+j){
				if(dp[u]!=2e9){
					dp2[u]=dp[u];
					pq.push({dp2[u],u});
				}
				dp[u]=dp2[x]+j;
			}
			else if(dp2[u]>dp2[x]+j){
				dp2[u]=dp2[x]+j;
				pq.push({dp2[u],u});
			}
		}
	}
	return dp2[0];
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[]){
	fall(i,0,m-1){
		int a=R[i][0],b=R[i][1];
		g[a].pb({b,L[i]}),g[b].pb({a,L[i]});
	}

	fall(i,0,K-1) ex[P[i]]=1;
	
	return djk(n);
}

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