FunctionRacerProblemsRace

Cheapest Toll Trip

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems