| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1096115 | 2024-10-03T20:57:11 Z | I_FloPPed21 | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+1;
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],long long 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]=1e11;
}
priority_queue<coada,vector<coada>,compare>pq;
for(int i=0;i<k;i++)
{
best[p[i]][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();
for(auto u:adj[nod])
{
if(best[u.unde][0]>cost+u.cost)
{
best[u.unde][1]=best[u.unde][0];
best[u.unde][0]=cost+u.cost;
pq.push({u.unde,best[u.unde][1]});
}
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];
}