Fewest tolls on the way

Scenario

A maps app has an "avoid tolls" setting. The region has n towns, numbered 0 to n - 1. A road joins two towns and can be driven both ways. Each road is either free or has a toll, and every tolled road charges one toll, whatever its length.

You work on the route planner. When a driver asks to avoid tolls, the app plans the trip with the fewest tolled roads, even if it is much longer. It also shows how many tolls remain.

Your task

Write fewest_tolls(n, roads, start, target).

n is the number of towns.
roads[i] = [a, b, toll] is a road between towns a and b. toll is 1 for a tolled road and 0 for a free road.
start is the town where the trip begins and target is where it ends.
Return the fewest tolled roads on any trip from start to target. Return -1 when target cannot be reached.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 5, roads = [[0, 1, 1], [1, 4, 1], [0, 2, 0], [2, 3, 0], [3, 4, 1]], start = 0, target = 4
Output: 1

Each heap entry is (tolls so far, town). A free road adds 0, so it never makes the count worse.

Taken from the heap	Roads relaxed	Heap after
(0, town 0)	to 1 gives 1, to 2 gives 0	(0, 2), (1, 1)
(0, town 2)	to 3 gives 0	(0, 3), (1, 1)
(0, town 3)	to 4 gives 1	(1, 1), (1, 4)
(1, town 1)	to 4 would give 2: not better	(1, 4)
(1, town 4)	the target: stop

The free roads 0, 2, 3 and then one tolled road into 4 give 1 toll. Going through town 1 costs 2.

Example 2#

text2 lines

Input:  n = 3, roads = [[0, 1, 1]], start = 0, target = 2
Output: -1

No road reaches town 2.

Example 3#

text2 lines

Input:  n = 1, roads = [], start = 0, target = 0
Output: 0

The trip starts where it ends, so there is nothing to pay.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(roads) ≤ 200,000, and every road is [a, b, toll] with 0 ≤ a, b < n, a ≠ b and toll equal to 0 or 1
0 ≤ start, target < n

What does n ≤ 10^5 tell you?

There can be 100,000 towns and 200,000 roads, so 400,000 directed edges to relax. Dijkstra with a heap does that in a few million steps. Going over all the roads again and again until nothing improves can take one pass per town on a long free chain, which is billions of steps.

Scenario

You work on the route planner. When a driver asks to avoid tolls, the app plans the trip with the fewest tolled roads, even if it is much longer. It also shows how many tolls remain.

Your task

Write fewest_tolls(n, roads, start, target).

n is the number of towns.
roads[i] = [a, b, toll] is a road between towns a and b. toll is 1 for a tolled road and 0 for a free road.
start is the town where the trip begins and target is where it ends.
Return the fewest tolled roads on any trip from start to target. Return -1 when target cannot be reached.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 5, roads = [[0, 1, 1], [1, 4, 1], [0, 2, 0], [2, 3, 0], [3, 4, 1]], start = 0, target = 4
Output: 1

Each heap entry is (tolls so far, town). A free road adds 0, so it never makes the count worse.

Taken from the heap	Roads relaxed	Heap after
(0, town 0)	to 1 gives 1, to 2 gives 0	(0, 2), (1, 1)
(0, town 2)	to 3 gives 0	(0, 3), (1, 1)
(0, town 3)	to 4 gives 1	(1, 1), (1, 4)
(1, town 1)	to 4 would give 2: not better	(1, 4)
(1, town 4)	the target: stop

The free roads 0, 2, 3 and then one tolled road into 4 give 1 toll. Going through town 1 costs 2.

Example 2#

text2 lines

Input:  n = 3, roads = [[0, 1, 1]], start = 0, target = 2
Output: -1

No road reaches town 2.

Example 3#

text2 lines

Input:  n = 1, roads = [], start = 0, target = 0
Output: 0

The trip starts where it ends, so there is nothing to pay.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(roads) ≤ 200,000, and every road is [a, b, toll] with 0 ≤ a, b < n, a ≠ b and toll equal to 0 or 1
0 ≤ start, target < n

What does n ≤ 10^5 tell you?