You are given a map of a road network with N intersections numbered from 0 to N – 1.
There are M road segments, and each segment connects two intersections, say u and v. All road segments are bidirectional. However, each road segment was originally designed with a primary direction of travel in mind. For example, a segment between u and v might have the primary direction set as u to v.
Traveling along a segment in its primary direction is considered a standard movement. Traveling along a segment in the opposite direction of its primary design is possible but requires extra effort, termed a violation.
Given the network, the primary directions of all roads [[u1, v1], [u2, v2], ...], a start intersection, and an end intersection, find a route from start to end that requires the minimum total number of violations.
This is a shortest-path problem on a graph where each road can be traversed in both directions, but moving along the road's primary direction costs 0 while moving against it costs 1. A clean solution is to build a weighted directed graph with 0/1 edge weights and run 0-1 BFS, or Dijkstra if preferred. The answer is the minimum total number of violations needed to travel from the start intersection to the end intersection.
