Cheapest Toll Trip
There are n towns numbered 0 to n - 1. roads is a list of entries [a, b, toll]: a one-way road from town a to town b that costs toll to drive. Several roads may link the same pair of towns, possibly with different tolls, and the road back may not exist.
Return the smallest total toll for a trip from start to finish. Return 0 when start == finish and -1 when no trip is possible.
Example 1
n 4
roads [[0,1,5],[1,3,5],[0,2,2],[2,3,20]]
start 0
finish 3
returns 10
Driving 0 to 1 to 3 costs 5 + 5 = 10; the road through town 2 would cost 2 + 20 = 22.
Example 2
n 3
roads [[0,1,7],[2,1,3]]
start 0
finish 2
returns -1
The only road into town 2 does not exist; the road listed goes out of town 2.
Constraints
1 <= n <= 500 <= len(roads) <= 100roads[i] = [a, b, toll]with0 <= a, b < n,a != band1 <= toll <= 1000 <= start, finish < n
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Connect All OfficesMedium
- Count the Shortest RoutesMedium
- Forced SidesMedium
- Largest PatchMedium
- Longest TrailMedium
- Lowest High PassMedium
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium