Proficient.
Put your skills to the test.

Problem summary

Travel from intersection a to b, minimizing streets traversed against their directed orientation. Each reversed street costs one violation.

Constraints

n ≤ 200000; at most 400000 streets; at most one street in either direction between a pair.

Worked example

An independently prepared example for this explanation.

4 1 4
4 3
3 2
1 2
4 2

1

Solution analysis

1. Replace each directed street p→q by a zero-cost arc p→q and a unit-cost arc q→p. Every allowed journey then has total cost equal to its number of violations.
2. Use 0-1 BFS: relax a zero-cost improvement at the front of a deque and a unit-cost improvement at the back. This maintains the same distance ordering as Dijkstra’s algorithm for weights zero and one.
3. In the example, 1→2 is free and traversing 2→4 reverses the street 4→2 once. Hence a route with one violation exists. No all-forward route reaches 4, so the minimum is one.

Why it works

The arc construction gives a cost-preserving correspondence between journeys and graph paths. 0-1 BFS processes distance layers in nondecreasing order because new distances differ from the current one by only zero or one. Its shortest path distance therefore minimizes violations; an infinite distance means no route.

Watch out. Read streets until EOF; no edge count is provided. A reversed edge costs one, irrespective of its length.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<deque>
#include<utility>
// Algorithm: Replace each directed street p→q by a zero-cost arc p→q and a unit-cost arc q→p.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,start,target;
    cin>>n>>start>>target;
    vector<vector<pair<int,int>>>graph(n+1);
    int from,to;
    while(cin>>from>>to){
        graph[from].push_back({to,0});
        graph[to].push_back({from,1});
    }
    const int infinity=1000000000;
    vector<int>distance(n+1,infinity);
    vector<bool>finished(n+1,false);
    deque<int>pending;
    distance[start]=0;
    pending.push_front(start);
    while(!pending.empty()){
        int vertex=pending.front();
        pending.pop_front();
        if(finished[vertex]){
            continue;
        }
        finished[vertex]=true;
        for(auto edge:graph[vertex]){
            int next=edge.first,weight=edge.second;
            if(distance[next]>distance[vertex]+weight){
                distance[next]=distance[vertex]+weight;
                if(weight==0){
                    pending.push_front(next);
                }
                else{
                    pending.push_back(next);
                }
            }
        }
    }
    if(distance[target]==infinity){
        cout<<"X\n";
    }
    else{
        cout<<distance[target]<<'\n';
    }
}