1930. Ivan's Car - Timus

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

class heap {
    public:
        int cost, node, last;

        bool operator < (const heap &A) const {
            return A.cost < cost;
        }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector < vector < pair < int , int > > > G(N + 1);
    while(M--) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v, 0);
        G[v].emplace_back(u, 1);
    }
    int start, stop;
    cin >> start >> stop;
    priority_queue < heap > Q;
    vector < int > d(N + 1, INF);
    d[start] = 0;
    Q.push(heap{0, start, -1});
    while(!Q.empty()) {
        int node = Q.top().node,
            last = Q.top().last;
        Q.pop();
        for(auto next : G[node]) {
            int C = 1;
            if(last == next.second || last == -1)
                C = 0;
            if(d[next.first] > d[node] + C) {
                d[next.first] = d[node] + C;
                Q.push(heap{d[next.first], next.first, next.second});
            }
        }
    }
    cout << d[stop];
}