| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1090692 | AlgorithmWarrior | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
int N,M,K;
struct edge
{
int nod;
long long len;
};
class cmp
{
public:
bool operator()(edge a,edge b)
{
return a.len>b.len;
}
};
vector<edge>G[MAX];
priority_queue<edge,vector<edge>,cmp>pq;
long long dist1[MAX],dist2[MAX];
void read()
{
cin>>N>>M>>K;
while(M--)
{
int nod1,nod2,len;
cin>>nod1>>nod2>>len;
++nod1;
++nod2;
G[nod1].push_back({nod2,len});
G[nod2].push_back({nod1,len});
}
int i;
for(i=1;i<=N;++i)
dist1[i]=dist2[i]=1e18;
while(K--)
{
int nod;
cin>>nod;
++nod;
dist1[nod]=dist2[nod]=0;
pq.push({nod,0});
}
}
void djikstra()
{
while(!pq.empty())
{
int nod=pq.top().nod;
long long len=pq.top().len;
pq.pop();
if(len>dist2[nod])
continue;
for(auto per : G[nod])
{
int nod2=per.nod;
int len2=per.len;
if(dist2[nod2]>len+len2)
{
if(dist1[nod2]>len+len2)
{
dist2[nod2]=dist1[nod2];
dist1[nod2]=len+len2;
}
else
dist2[nod2]=len+len2;
pq.push({nod2,dist2[nod2]});
}
}
}
}
void write()
{
cout<<dist2[1];
}
int main()
{
read();
djikstra();
write();
return 0;
}