# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1255654 | notisora | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long
using namespace std;
const int N=1e5+2;
vector<pair<int,int>>adj[N];
int n,m,k;
bool isexit[N];
ll d[N];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("i.INP","r",stdin);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b,w;
cin>>a>>b>>w;
adj[a].pb({b,w});
adj[b].pb({a,w});
}
for(int i=1;i<=k;i++){
int s;
cin>>s;
isexit[s]=1;
}
for(int i=0;i<n;i++) d[i]=1e15;
for(int s=0;s<n;s++){
sort(adj[s].begin(),adj[s].end(),[&](pair<int,int>&A,pair<int,int>&B){
if (isexit[A.fi] != isexit[B.fi])
return isexit[A.fi] > isexit[B.fi];
return A.se < B.se;
});
// cout<<s<<": ";
// for(pair<int,int>&pr:adj[s]){
// cout<<pr.fi<<" ";
// }
// cout<<el;
}
pq.push({0LL,0});
d[0]=0;
while(!pq.empty()){
ll dis=pq.top().fi;
int s=pq.top().se;
pq.pop();
if (dis>d[s]) continue;
// cout<<el;
for(int i=1;i<(int)adj[s].size();i++){
pair<int,int>&pr=adj[s][i];
int u=pr.fi;
int w=pr.se;
if (d[u]>dis+(ll)w){
d[u]=dis+(ll)w;
pq.push({d[u],u});
}
}
}
ll ans=1e15;
for(int i=0;i<n;i++){
if (isexit[i]){
// cout<<i<<" "<<d[i]<<el;
ans=min(ans,d[i]);
}
}
cout<<ans;
}