# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1263977 | dungsnfg | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
vector<vector<pair<int, ll>>> adj(N);
int u, v;
ll w;
for(int i = 0; i < M; i++){
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
vector<ll> T(N, INF);
vector<int> P(K);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
for(int i = 0; i < K; i++){
cin >> P[i];
T[P[i]] = 0;
pq.emplace(0LL, P[i]);
}
vector<ll> best1(N, INF), best2(N, INF);
while(!pq.empty()){
auto [curT, x] = pq.top();
pq.pop();
if (curT != T[x]) continue;
for(auto &[nei, len] : adj[x]){
ll candidate = curT + len;
if (candidate < best1[nei]) {
best2[nei] = best1[nei];
best1[nei] = candidate;
}
else if (candidate < best2[nei]) {
best2[nei] = candidate;
}
ll newT = best2[nei];
if (newT < T[nei]) {
T[nei] = newT;
pq.emplace(T[nei], nei);
}
}
}
cout << T[0] << "\n";
return 0;
}