{x}
blog image

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.

 

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
Explanation: The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.

Example 2:

Input: maxTime = 29, 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: 48
Explanation: The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.

Example 3:

Input: maxTime = 25, 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: -1
Explanation: There is no way to reach city 5 from city 0 within 25 minutes.

 

Constraints:

  • 1 <= maxTime <= 1000
  • n == passingFees.length
  • 2 <= n <= 1000
  • n - 1 <= edges.length <= 1000
  • 0 <= xi, yi <= n - 1
  • 1 <= timei <= 1000
  • 1 <= passingFees[j] <= 1000 
  • The graph may contain multiple edges between two nodes.
  • The graph does not contain self loops.

Minimum Cost to Reach Destination in Time

This problem involves finding the minimum cost to travel from city 0 to city n-1 within a given time limit, considering passing fees at each city and travel times between cities. The solution presented uses dynamic programming.

Approach: Dynamic Programming

The core idea is to build a table f[i][j] where f[i][j] represents the minimum cost to reach city j within i minutes. We iterate through all possible times (up to maxTime) and edges, updating the minimum cost to reach each city at each time step.

  1. Initialization:

    • f[0][0] = passingFees[0] (The cost to reach city 0 at time 0 is its passing fee).
    • All other entries in f are initialized to infinity, representing unreachable states.

  2. Iteration:

    • We iterate through times from 1 to maxTime.
    • For each edge (x, y, time):
      • If the travel time time is less than or equal to the current time i:
        • We check if reaching city x via city y is cheaper: f[i][x] = min(f[i][x], f[i - time][y] + passingFees[x]).
        • Similarly, we check if reaching city y via city x is cheaper: f[i][y] = min(f[i][y], f[i - time][x] + passingFees[y]).

  3. Result:

    • After iterating through all times and edges, the minimum cost to reach the destination city (n-1) within maxTime is the minimum value among f[i][n-1] for all i from 0 to maxTime.
    • If this minimum value is still infinity, it means the destination is unreachable within the time limit, and we return -1.

Time and Space Complexity Analysis

  • Time Complexity: O(maxTime * (m + n)), where m is the number of edges and n is the number of cities. This is because we iterate through each time step (maxTime), and for each time step, we iterate through all edges (m) and potentially update the cost for each city (n). The nested loops dominate the runtime.

  • Space Complexity: O(maxTime * n). This is due to the f table which stores the minimum cost to reach each city at each time step.

Code Implementation (Python3)

import sys
 
def minCost(maxTime: int, edges: list[list[int]], passingFees: list[int]) -> int:
    n = len(passingFees)
    dp = [[sys.maxsize] * n for _ in range(maxTime + 1)]  # Initialize DP table
    dp[0][0] = passingFees[0]  # Base case: cost to reach city 0 at time 0
 
    for i in range(1, maxTime + 1):
        for u, v, t in edges:
            if t <= i:
                dp[i][u] = min(dp[i][u], dp[i - t][v] + passingFees[u])
                dp[i][v] = min(dp[i][v], dp[i - t][u] + passingFees[v])
 
    min_cost = min(dp[i][n - 1] for i in range(maxTime + 1))
    return min_cost if min_cost != sys.maxsize else -1

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, adapting the syntax and data structures to each respective language. The core algorithmic logic remains consistent across all implementations.