Show problems as
Classic problem #1928HardArrayDynamic ProgrammingGraph TheoryDijkstra's Algorithm

Minimum Cost to Reach Destination in Time

Real-world version: Cheapest Run Inside The Shift
Tracked in this browser only
Read Minimum Cost to Reach Destination in Time on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier starts at depot 0 and must finish at depot n - 1, where n is the length of tolls. Each row of links is [a, b, minutes], a road that can be driven in either direction and takes minutes to drive. Two depots may be joined by more than one road, and no road loops a depot back to itself.

tolls[j] is the gate charge at depot j. The charge is paid on arriving at a depot, and it is paid again on every later arrival there, so a depot passed through twice is charged twice. The charge at the starting depot is paid before setting off.

The whole run must take at most budget minutes of driving; time spent standing at a depot does not count. Return the smallest total of gate charges for a run that finishes at depot n - 1 inside the budget, or -1 if no run manages it. Gate charges are at least 1, so a real total is never -1.

Examples

Example 1

Input
budget = 8, links = [[0, 1, 1], [1, 3, 1], [0, 2, 4], [2, 3, 4]], tolls = [2, 40, 3, 5]
Output
10

With 8 minutes to play with the courier can drive 0 to 2 to 3, taking all 8 minutes and paying 2 at the start, 3 at depot 2 and 5 at depot 3.

Example 2

Input
budget = 2, links = [[0, 1, 1], [1, 3, 1], [0, 2, 4], [2, 3, 4]], tolls = [2, 40, 3, 5]
Output
47

Only 2 minutes are available, so the run 0 to 1 to 3 is the one that fits, paying 2 then 40 then 5.

Example 3

Input
budget = 5, links = [[0, 1, 6], [1, 2, 1]], tolls = [4, 7, 9]
Output
-1

The only road out of depot 0 takes 6 minutes on its own, which is already past the budget, so the courier cannot finish the run.

Constraints

  • 1 <= budget <= 1000
  • n == tolls.length
  • 2 <= n <= 1000
  • n - 1 <= links.length <= 1000
  • links[i].length == 3
  • 0 <= a_i, b_i <= n - 1
  • a_i != b_i
  • 1 <= minutes_i <= 1000
  • 1 <= tolls[j] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def cheapest_run(budget: int, links: list[list[int]], tolls: list[int]) -> int:
Java
public int cheapestRun(int budget, int[][] links, int[] tolls)

More on the same topics