# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1182462 | boclobanchat | 악어의 지하 도시 (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include"crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long,long long>
#define fi first
#define se second
const int MAXN=1e5+5;
const long long INF=1e18;
long long dp[MAXN][2];
vector<ii> ds[MAXN];
long long travel_plan(int n,int m,int R[][2],int L[],int k,int P[])
{
priority_queue< ii,vector<ii>,greater<ii> > pq;
for(int i=0;i<n;i++) dp[i][0]=dp[i][1]=INF,ds[i].clear();
for(int i=0;i<m;i++) ds[R[i][0]].push_back({R[i][1],L[i]}),ds[R[i][1]].push_back({R[i][0],L[i]});
for(int i=0;i<k;i++) dp[P[i]][0]=dp[P[i]][1]=0,pq.push({0,P[i]});
while(!pq.empty())
{
long long a=pq.top().fi,b=pq.top().se;
pq.pop();
if(dp[b][1]<a) continue;
for(auto v:ds[b]) if(dp[v.fi][0]>a+v.se)
{
dp[v.fi][1]=dp[v.fi][0],dp[v.fi][0]=a+v.se;
pq.push({dp[v.fi][1],v.fi});
}
else if(dp[v.fi][1]>a+v.se)
{
dp[v.fi][1]=a+v.se;
pq.push({dp[v.fi][1],v.fi});
}
}
return dp[0][1];
}