【AtCoder】ABC 481 D - Autopilot

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr int INF = 1e+9;
7. 
8.template <class T>
9.using Graph = vector<vector<T>>;
10. 
11.template <typename T>
12.inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
13. 
14.// ======================================== //
15. 
16.int main()
17.{
18.    int N, M, S, T;
19.    cin >> N >> M >> S >> T;
20.    Graph<int> G(N);
21.    vector<int> min_v(N, INF);
22.    rep(i, 0, M) {
23.        int A, B;
24.        cin >> A >> B;
25.        A--;
26.        B--;
27.        G[A].push_back(B);
28.        chmin(min_v[A], B);
29.    }
30. 
31.    vector<int> dist(N, INF);
32.    deque<int> que;
33.    dist[S - 1] = 0;
34.    que.push_back(S - 1);
35.    while (!que.empty()) {
36.        int now = que.front();
37.        que.pop_front();
38. 
39.        for (auto next : G[now]) {
40.            int cost = (next == min_v[now] ? 0 : 1);
41. 
42.            if (dist[next] > dist[now] + cost) {
43.                dist[next] = dist[now] + cost;
44. 
45.                if (cost == 0) {
46.                    que.push_front(next);
47.                }
48.                else {
49.                    que.push_back(next);
50.                }
51.            }
52.        }
53.    }
54. 
55.    if (dist[T - 1] == INF) {
56.        cout << -1 << endl;
57.    }
58.    else {
59.        cout << dist[T - 1] << endl;
60.    }
61. 
62.    return 0;
63.}