Submission #6171517

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;

int solve(int n, int m, const vector<vector<int> > & g, int start, int goal) {
    vector<array<int, 3> > dist(n, { INT_MAX, INT_MAX, INT_MAX });
    queue<pair<int, int> > que;
    auto push = [&](int x, int y, int d) {
        if (dist[x][y] != INT_MAX) return;
        dist[x][y] = d;
        que.emplace(x, y);
    };
    push(start, 0, 0);
    while (not que.empty()) {
        int x, y; tie(x, y) = que.front();
        que.pop();
        for (int z : g[x]) {
            push(z, (y + 1) % 3, dist[x][y] + 1);
        }
    }
    if (dist[goal][0] == INT_MAX) return -1;
    assert (dist[goal][0] % 3 == 0);
    return dist[goal][0] / 3;
}

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n);
    REP (i, m) {
        int u, v; cin >> u >> v;
        -- u; -- v;
        g[u].push_back(v);
    }
    int s, t; cin >> s >> t;
    -- s; -- t;
    cout << solve(n, m, g, s, t) << endl;
    return 0;
}

Submission Info

Judge Result