Toll Route With Passes

HardAdvanced Graphs

Problem

A driver crosses a region with n towns. Each roads[i] = [u, v, toll] is a two-way road with a toll. The driver owns passes toll passes; using one on a road makes that road free (one pass per road crossing).

Return the minimum total toll to drive from town src to town dst, or -1 if dst cannot be reached.

Example 1

Input:
n = 4, roads = [[0,1,10],[1,3,10],[0,2,1],[2,3,25]], src = 0, dst = 3, passes = 1
Output:
1

Drive 0 → 2 for 1 and use the pass on the 25 road. The other route would cost 10 even with the pass.

Example 2

Input:
same roads, passes = 0
Output:
20

Example 3

Input:
n = 3, roads = [[0,1,5]], src = 0, dst = 2, passes = 3
Output:
-1

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ roads.length ≤ 2·10^4
  • 1 ≤ toll ≤ 10^4
  • 0 ≤ passes ≤ 10

Hint

Show the first hint

The best route depends not only on where you are but also on how many passes are left.

Walkthrough

How to approach it

01Clarify before coding

  • Are roads two-way? Yes.
  • Must every pass be used? No, at most passes of them.
  • Can src equal dst? Yes: the toll is 0.

02Brute force

Enumerate simple paths and, on each, make the passes most expensive roads free.

Cost: Exponential number of paths.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.