lessons/参考实现/05-最短路与类最短路/AtCoder-abc277_e.cpp

#include <deque>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
using namespace std;
struct Edge { int to, cost; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    auto id = [n](int v, int mode) { return v + mode * n; };
    vector<vector<Edge>> g(2 * n);
    for (int i = 0; i < m; ++i) {
        int u, v, a; cin >> u >> v >> a; --u; --v;
        g[id(u, a)].push_back({id(v, a), 1});
        g[id(v, a)].push_back({id(u, a), 1});
    }
    for (int i = 0; i < k; ++i) {
        int v; cin >> v; --v;
        g[id(v, 0)].push_back({id(v, 1), 0});
        g[id(v, 1)].push_back({id(v, 0), 0});
    }
    const int inf = numeric_limits<int>::max() / 4;
    vector<int> dist(2 * n, inf); vector<bool> done(2 * n, false); deque<int> dq;
    dist[id(0, 1)] = 0; dq.push_front(id(0, 1));
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        if (done[u]) continue;
        done[u] = true;
        for (Edge e : g[u]) if (dist[e.to] > dist[u] + e.cost) {
            dist[e.to] = dist[u] + e.cost;
            if (e.cost == 0) dq.push_front(e.to); else dq.push_back(e.to);
        }
    }
    int answer = min(dist[id(n - 1, 0)], dist[id(n - 1, 1)]);
    cout << (answer == inf ? -1 : answer) << '\n';
}