| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1331333 | Mamikonm1 | 악어의 지하 도시 (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
const int n=1e5+5;
const ll inf=1e18;
pair<ll,ll> dp[n];
vector<pair<int,int>>graph[n];
bool add(pair<ll,ll>&a,ll x){
V<ll>st={a.first,a.second,x};
sort(begin(st),end(st));
if(make_pair(st[0],st[1])==a)return 0;
a=make_pair(st[0],st[1]);
return 1;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<N;++i)
dp[i]={inf,inf};
int u,v;
for(int i=0;i<M;++i){
u=R[i][0];v=R[i][1];
graph[u].push_back({v,L[i]});
graph[v].push_back({u,L[i]});
}
priority_queue<pair<pair<ll,ll>,int>,vector<pair<pair<ll,ll>,int>>,greater<>>q;
for(int i=0;i<K;++i){
u=P[i];
dp[u]={0,0};
q.push({dp[u],u});
}
bool vis[n+1];
ll w;
while(!q.empty()){
u=q.top().second;
w=q.top().first.first;
assert(dp[u].first<=dp[u].second);
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto&i:graph[u]){
v=i.first;
bool ok=0;
if(add(dp[v],i.second+w))q.push({{dp[v].second,dp[v].first},v});
}
}
for(int i=0;i<n;++i)assert(dp[i].first<=dp[i].second);
return dp[0].second;
}