lessons/参考实现/05-最短路与类最短路/CodeForces-59E.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u);
    }
    int width = n + 1;
    auto state = [width](int previous, int current) { return previous * width + current; };
    auto triple = [width](int a, int b, int c) {
        return (static_cast<long long>(a) * width + b) * width + c;
    };
    unordered_set<long long> forbidden;
    forbidden.reserve(static_cast<size_t>(k) * 2 + 1);
    while (k--) { int a, b, c; cin >> a >> b >> c; forbidden.insert(triple(a, b, c)); }

    int states = width * width;
    vector<int> dist(states, -1), parent(states, -1);
    int start = state(0, 1), target = -1;
    queue<int> q; q.push(start); dist[start] = 0;
    while (!q.empty() && target == -1) {
        int id = q.front(); q.pop();
        int previous = id / width, current = id % width;
        for (int next : g[current]) {
            if (forbidden.count(triple(previous, current, next))) continue;
            int next_state = state(current, next);
            if (dist[next_state] != -1) continue;
            dist[next_state] = dist[id] + 1;
            parent[next_state] = id;
            if (next == n) { target = next_state; break; }
            q.push(next_state);
        }
    }
    if (target == -1) { cout << "-1\n"; return 0; }
    vector<int> path;
    for (int id = target; id != -1; id = parent[id]) path.push_back(id % width);
    reverse(path.begin(), path.end());
    cout << path.size() - 1 << '\n';
    for (int v : path) cout << v << ' ';
    cout << '\n';
}