Problem statement

https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/

Solution 1

The problem is very similar to 0787 Cheapest Flights Within K Stops. The idea is to use Dijktra algorihm,

Complexity

Time complexity is O(n*m*log(mn)), where n is number of nodes, m is maximum time.

Code

class Solution:
    def minCost(self, maxTime, edges, F):
        n, times = len(F), [float('inf')]*(len(F)), 
        graph, heap = defaultdict(list), [(F[0],0,0)]
        
        for i, j, w in edges: 
            graph[i].append([j, w])
            graph[j].append([i, w])
            
        while heap:
            cost, node, time = heappop(heap)
            if time > maxTime: continue
            if node == n-1: return cost
            
            if time < times[node]:
                times[node] = time
                for neib, trip in graph[node]:
                    heappush(heap, (F[neib] + cost, neib, time + trip))
            
        return -1

Solution 2

Let dp[i][j] be the minimum cost to reach node i in time j.

Complexity

It is O(E*m), but in practice it works slower, need to investigate. The reason why it works so slow is that we jump between indexes a lot I think.

Code

class Solution:
    def minCost(self, maxTime, edges, F):
        n = len(F)
        dp = [[float('inf')] * n for j in range(maxTime + 1)]
        dp[0][0] = 0
        for i in range(1, maxTime + 1):
            dp[i] = dp[i-1][:]
            for v, w, time in edges:
                if time <= i:
                    dp[i][w] = min(dp[i][w], dp[i-time][v] + F[w])
                    dp[i][v] = min(dp[i][v], dp[i-time][w] + F[v])
        
        cand = dp[-1][-1] + F[0] 
        return cand if cand != float("inf") else -1