IOI '11 P4 - Crocodile's Underground City (Standard I/O)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 2e9;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, l; cin >> u >> v >> l;
        g[u].emplace_back(v, l);
        g[v].emplace_back(u, l);
    }

    vector<int> dist(n, INF); // worst case
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> haveOption(n);
    for (int i = 0; i < k; ++i) {
        int x; cin >> x;
        dist[x] = 0;
        pq.emplace(0, x);
    }
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (dist[v] && dist[v] != INF) continue;
        if (d && !haveOption[v]) {
            haveOption[v] = true;
            continue;
        }
        dist[v] = d;
        if (v == 0) break;
        for (auto [u, l] : g[v]) {
            if (dist[u] == INF) pq.emplace(d+l, u);
        }
    }
    cout << dist[0] << endl;
    return 0;
}