Minimum Cost to Reach Destination in Time LeetCode solution in Python

1
class Solution:
2
    def minCost(
3
        self, maxTime: int, edges: List[List[int]], passingFees: List[int]
4
    ) -> int:
5
        """
6
        Time: O((m+n)* maxtime), where m is length of edges
7
        Space: O(n*maxtime)
8
        """
9
        n = len(passingFees)
10
        dp = [[math.inf] * (n) for _ in range(maxTime + 1)]
11
        dp[0][0] = passingFees[0]
12

13
        ans = math.inf
14
        for k in range(1, maxTime + 1):
15
            for x, y, time in edges:
16
                if k >= time:
17
                    # dual direction
18
                    dp[k][y] = min(dp[k][y], dp[k - time][x] + passingFees[y])
19
                    dp[k][x] = min(dp[k][x], dp[k - time][y] + passingFees[x])
20

21
            ans = min(ans, dp[k][n - 1])
22

23
        if ans == math.inf:
24
            return -1
25
        return ans