| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 758266 | 2023-06-14T10:40:31 Z | ivaziva | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
long long n;
long long m;
long long k;
vector<pair<long long,long long>> adj[MAXN];
long long pos[MAXN];
priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
long long dist1[MAXN];
long long dist2[MAXN];
long long niz[MAXN];
int main()
{
cin>>n>>m>>k;
for (long long i=1;i<=m;i++)
{
long long x;
long long y;
long long z;
cin>>x>>y>>z;
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
for (long long i=0;i<MAXN;i++)
{
dist1[i]=LLONG_MAX;
dist2[i]=LLONG_MAX;
}
for (long long i=1;i<=k;i++)
{
cin>>niz[i];
dist1[niz[i]]=0;
dist2[niz[i]]=0;
pq.push({0,niz[i]});
pos[niz[i]]=1;
}
while (pq.empty()==false)
{
long long node0=pq.top().second;
long long dist0=pq.top().first;
pq.pop();
if (dist2[node0]<dist0) continue;
if (pos[node0]>1) continue;
if (pos[node0]==1)
{
long long s=adj[node0].size();
for (long long i=0;i<s;i++)
{
long long node=adj[node0][i].first;
long long dist=adj[node0][i].second;
if (dist0+dist<dist1[node])
{
dist2[node]=dist1[node];
dist1[node]=dist0+dist;
pq.push({dist1[node],node});
}
else if (dist0+dist<dist2[node])
{
dist2[node]=dist+dist0;
pq.push({dist2[node],node});
}
}
}
pos[node0]++;
}
cout<<dist2[0]<<endl;
}