| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1096132 | 2024-10-03T21:19:35 Z | I_FloPPed21 | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+1;
const long long inf=1e18;
struct nod
{
int unde;
long long cost;
};
struct coada
{
int unde;
long long cost;
};
struct compare
{
bool operator()(coada &x,coada &y)
{
return x.cost>y.cost;
}
};
vector<nod>adj[N];
long long best[N][2];
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
for(int i=0; i<m; i++)
{
adj[r[i][0]].push_back({r[i][1],l[i]});
adj[r[i][1]].push_back({r[i][0],l[i]});
}
for(int i=0; i<n; i++)
{
best[i][0]=best[i][1]=inf;
}
priority_queue<coada,vector<coada>,compare>pq;
for(int i=0; i<k; i++)
{
best[p[i]][0]=0;
best[p[i]][1]=0;
pq.push({p[i],0});
}
while(!pq.empty())
{
int nod=pq.top().unde;
long long cost=pq.top().cost;
pq.pop();
if(cost!=best[nod][1])
continue;
for(auto u:adj[nod])
{
if(best[u.unde][0]>cost+u.cost)
{
if(best[unde][1]!=best[unde][0])
{
best[u.unde][1]=best[u.unde][0];
if(best[u.unde][1]!=inf)
pq.push({u.unde,best[u.unde][1]});
}
best[u.unde][0]=cost+u.cost;
}
else if(best[u.unde][1]>cost+u.cost)
{
best[u.unde][1]=cost+u.cost;
pq.push({u.unde,best[u.unde][1]});
}
}
}
return best[0][1];
}