1928. Minimum Cost to Reach Destination in Time

There is a country of n cities numbered from 0 to n - 1 where all the cities are connected by bi-directional roads. The roads are represented as a 2D integer array edges where edges[i] = [xi, yi, timei] denotes a road between cities xi and yi that takes timei minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.

Each time you pass through a city, you must pay a passing fee. This is represented as a 0-indexed integer array passingFees of length n where passingFees[j] is the amount of dollars you must pay when you pass through city j.

In the beginning, you are at city 0 and want to reach city n - 1 in maxTime minutes or less. The cost of your journey is the summation of passing fees for each city that you passed through at some moment of your journey (including the source and destination cities).

Given maxTime, edges, and passingFees, return the minimum cost to complete your journey, or -1 if you cannot complete it within maxTime minutes.

Modified Dijkstra

def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:  
    from heapq import heapify, heappush, heappop  
    h = [(passingFees[0], 0, 0)]  
    n = len(passingFees)  
      
    g = collections.defaultdict(list)  
    for a, b, time in edges:  
        g[a].append((b, time))  
        g[b].append((a, time))  
      
    mintime = [float('inf')] * n  
    minfee = [float('inf')] * n  
      
    while h:  
        curfee, curtime, city = heappop(h)  
        if city == n - 1:  
            return curfee  
          
        for dst, time in g[city]:  
            fee = passingFees[dst]  
            if curtime + time > maxTime:  
                continue  
            if curtime + time < mintime[dst] or curfee + fee < minfee[dst]:  
                # Because the cities are arranged based on cost, the city with low cost will always be encountered first. The only way we will see the city the second time is when the time is smaller  
                heappush(h, (curfee + fee, curtime + time, dst))  
                mintime[dst] = curtime + time  
                minfee[dst] = curfee + fee 
                  
    return -1

Learning On the Way

Modified Dijkstra