# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216242 | escobrand | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long
#define fi first
#define se second
int t,n,i,m,M,u,v;
const int maxn = 1e5 + 10;
const ll inf = 1e15;
typedef pair<ll,ll> pii;
vector<pii> adj[maxn];
bool e[maxn],c[maxn];
ll d[maxn][2],tmp,w;
priority_queue<ll> dp[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>M;
while(m--)
{
cin>>u>>v>>w;
adj[u].eb({v,w});
adj[v].eb({u,w});
}
for(i = 0;i<n;i++)d[i][0] = d[i][1] = inf;
priority_queue<pii,vector<pii>,greater<>>q;
while(M--)
{
cin>>i;
e[i] = 1;
d[i][0] = d[i][1] = 0;
q.push({0,i});
}
while(q.size())
{
i = q.top().se;
w = q.top().fi;
q.pop();
if(c[i])continue;
c[i] = 1;
for(auto k : adj[i])
{
ll tmp = w + k.se;
if(d[k.fi][1] > tmp)
{
d[k.fi][1] = tmp;
if(d[k.fi][0] > d[k.fi][1])swap(d[k.fi][0] , d[k.fi][1]);
q.push({d[k.fi][1],k.fi});
}
}
}
cout<<d[0][1];
return 0;
}