# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1211879 | ackerman2840 | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const long long INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<pii>> adj(n);
for (int i = 0; i < m; ++i) {
int u, v, d;
cin >> u >> v >> d;
adj[u].push_back({v, d});
adj[v].push_back({u, d});
}
vector<long long> exits(k);
for (int i = 0; i < k; ++i) {
cin >> exits[i];
}
vector<array<long long, 2>> dist(n, {INF, INF});
priority_queue<pii> pq;
for (int i = 0; i < k; ++i) {
dist[exits[i]][0] = 0;
dist[exits[i]][1] = 0;
pq.push({0, exits[i]});
}
while (!pq.empty()) {
auto [neg_d, node] = pq.top(); pq.pop();
long long d = -neg_d;
if (dist[node][1] != d) continue;
for (auto [to, dd] : adj[node]) {
if (dist[to][0] > d + dd) {
if (dist[to][0] < dist[to][1]) {
pq.push({-dist[to][0], to});
}
dist[to][1] = dist[to][0];
dist[to][0] = d + dd;
} else if (dist[to][1] > d + dd) {
dist[to][1] = d + dd;
pq.push({-dist[to][1], to});
}
}
}
cout << dist[0][1] << "\n";
return 0;
}