1649. Fewest One-Way Streets to Turn Around
A city has n junctions and m ONE-WAY streets. You may order any street to
be reversed, at a cost of one notice per street. Print the fewest notices needed
before a legal drive exists from junction 1 to junction n, or -1 if no
number of notices can make one.
4 junctions, 1 -> 2, 3 -> 2, 4 -> 3 -> 2
Drive 1 to 2 as it stands, reverse 3 to 2, then reverse 4 to 3. Two notices.
## The four things that have to be said
directed? yes, that is the whole problem.
self-loops? allowed, and reversing one achieves nothing.
parallel streets? allowed, including two copies pointing opposite ways, in
which case one of them is already free to use.
disconnected? allowed. If 1 and n are in different pieces of the graph with
the arrows IGNORED, no amount of reversing helps, so print -1.
When n is 1 the answer is 0.
## What most people try first
Searching the graph as given and reporting failure when n cannot be reached.
That answers a different question: whether zero notices suffice.
The next instinct is to guess how many streets to reverse and try every subset.
With m at 100000 that is not a method, it is a joke, and it also misses the
point: the reversals you need are decided by the route you choose, so choose the
route and the reversals come with it.
## Turn it into a weighted graph, where the weights are 0 and 1
For every street u -> v put TWO edges into the search graph:
u -> v weight 0 drive it as it is
v -> u weight 1 reverse it first, then drive it
Now any walk from 1 to n in this new graph is a drive, and its total weight is
exactly the number of notices that drive needs. So the answer is the cheapest
walk, and every weight is 0 or 1.
That is why no amount of reversing can help when 1 and n lie in different
pieces of the UNDIRECTED graph: the doubled graph has an edge in both directions
across every street, so its reachable set from 1 is precisely vertex 1's
undirected component.
## The deque does it in one pass
dist[1] = 0, everything else infinite
deque holding 1
pop u from the FRONT
for each outgoing street u -> v: relax with weight 0, push v on the FRONT
for each incoming street w -> u: relax with weight 1, push w on the BACK
A front push always carries the distance just popped, which is already the
smallest in the deque, and a back push carries one more, which is already the
largest. So the deque stays sorted without ever comparing two keys, which is the
saving over a heap: O(n + m) rather than O(m log n).
## Cost
O(n + m). No route needs more than n - 1 reversals, so the answer stays
below 50000 and a 32 bit integer is ample.
Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n`
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v: a one-way street from u to v.
Output
Print one integer, the fewest streets that must be reversed before junction n can be driven to from junction 1, or -1 if no set of reversals makes that possible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.