Hard

Minimum Cost to Reach Destination in Time

LAB

Given undirected edges [u,v,time], passing fees, and maxTime, return the minimum fee to reach node n-1 in time, or -1.

EXAMPLES

Example 1

Input
{
  "maxTime": 30,
  "edges": [
    [
      0,
      1,
      10
    ],
    [
      1,
      2,
      10
    ],
    [
      2,
      5,
      10
    ],
    [
      0,
      3,
      1
    ],
    [
      3,
      4,
      10
    ],
    [
      4,
      5,
      15
    ]
  ],
  "passingFees": [
    5,
    1,
    2,
    20,
    20,
    3
  ]
}

Output
11

FUNCTION SHAPE

maxTime: intedges: intMatrixpassingFees: intArray→int

SOLUTION NOTE

Modified Dijkstra tracking both cost and time. Prune paths exceeding maxTime.

Reveal reference solution +

pythonREFERENCE

def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
    n = len(passingFees)
    graph = defaultdict(list)
    for u, v, t in edges:
        graph[u].append((v, t))
        graph[v].append((u, t))

    # (cost, time, node)
    heap = [(passingFees[0], 0, 0)]
    best_time = {0: 0}

    while heap:
        cost, time, node = heappop(heap)

        if node == n - 1:
            return cost

        for nei, t in graph[node]:
            new_time = time + t
            if new_time <= maxTime:
                if nei not in best_time or new_time < best_time[nei]:
                    best_time[nei] = new_time
                    heappush(heap, (cost + passingFees[nei], new_time, nei))

    return -1

TimeO(E × maxTime × log V)

SpaceO(V × maxTime)

Open on LeetCode ↗