HardNo. 1928
Minimum Cost to Reach Destination in Time — LeetCode 1928 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph, Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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
- Explanation
- The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.
Python solution
class Solution:
def minCost(
self, maxTime: int, edges: List[List[int]], passingFees: List[int]
) -> int:
m, n = maxTime, len(passingFees)
f = [[inf] * n for _ in range(m + 1)]
f[0][0] = passingFees[0]
for i in range(1, m + 1):
for x, y, t in edges:
if t <= i:
f[i][x] = min(f[i][x], f[i - t][y] + passingFees[x])
f[i][y] = min(f[i][y], f[i - t][x] + passingFees[y])
ans = min(f[i][n - 1] for i in range(m + 1))
return ans if ans < inf else -1Complexity
- Time
- O(maxTime × (m + n)), where m and n are the number of edges and cities, respectively
- Space · auxiliary
- O(maxTime × n)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1928. Minimum Cost to Reach Destination in Time is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0329 | Longest Increasing Path in a Matrix | Hard |
| 1728 | Cat and Mouse II | Hard |
| 2050 | Parallel Courses III | Hard |
| 2328 | Number of Increasing Paths in a Grid | Hard |
| 2646 | Minimize the Total Price of the Trips | Hard |
| 2977 | Minimum Cost to Convert String II | Hard |
Frequently asked questions
- How hard is LeetCode 1928. Minimum Cost to Reach Destination in Time?
LeetCode 1928. Minimum Cost to Reach Destination in Time is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1928. Minimum Cost to Reach Destination in Time?
The Python solution on this page runs in O(maxTime × (m + n)), where m and n are the number of edges and cities, respectively.
- What is the space complexity of LeetCode 1928. Minimum Cost to Reach Destination in Time?
The Python solution on this page uses O(maxTime × n) auxiliary space.
- What topics does LeetCode 1928. Minimum Cost to Reach Destination in Time cover?
LeetCode 1928. Minimum Cost to Reach Destination in Time is tagged Graph, Array and Dynamic Programming on LeetCode.