We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Reach Destination in Time

Number: 2040

Difficulty: Hard

Paid? No

Companies: Meta

Problem Description

Given a connected graph of n cities (numbered 0 to n - 1) with bidirectional roads where each road has an associated travel time, and each city has a passing fee, you begin at city 0 and want to reach city n - 1 within a maximum allowed travel time (maxTime). The cost of a journey is the sum of the passing fees for every city you pass through (including both the starting and the destination cities). The task is to determine the minimum cost to complete this journey within maxTime minutes. If it is impossible to reach the destination on time, return -1.

Key Insights

  • The problem requires minimizing cost while ensuring the total travel time does not exceed maxTime.
  • This is a multi-criteria shortest path problem where states are defined by both the current city and the time spent so far.
  • A modified Dijkstra algorithm can be applied, using a priority queue that prioritizes states based on cost.
  • Use a DP (or memoization) table to keep track of the minimum cost to reach each city with a given accumulated time, helping to prune non-optimal states.
  • The limited maxTime bounds make it feasible to track states on the time dimension.

Space and Time Complexity

Time Complexity: O(maxTime * E * log(maxTime * N)) in the worst-case scenario, where E is the number of edges and N is the number of cities. Space Complexity: O(N * maxTime) due to the DP table storing best cost values for each city at every possible time.

Solution

We solve the problem by modeling it as a state-space graph search where each state is represented by (current_city, current_time, accumulated_cost). A priority queue is used to always expand the state with the lowest cost first, ensuring that once we reach the destination, the cost is optimal. Whenever we explore a neighboring city, if the new accumulated time does not exceed maxTime and it leads to a better cost than previously recorded for that city at that time, we update our DP table and push the new state into the priority queue.

This approach effectively handles the dual constraints (minimizing cost and keeping track of used time) by maintaining best-known costs for every (city, time) state.

Code Solutions

import heapq

def minCost(maxTime, edges, passingFees):
    # Build the graph from edges as an adjacency list: city -> list of (neighbor, travel_time)
    n = len(passingFees)
    graph = [[] for _ in range(n)]
    for u, v, t in edges:
        graph[u].append((v, t))
        graph[v].append((u, t))
    
    # Create a DP table: dp[city][time] will store the minimal cost to get to 'city' at 'time'
    # Initialize with a large value (infinity)
    INF = float('inf')
    dp = [[INF] * (maxTime + 1) for _ in range(n)]
    # Starting state: at city 0 with time 0 and cost equal to passingFees[0]
    dp[0][0] = passingFees[0]
    
    # Priority queue: each entry is (cost, time, city)
    # We use cost as the priority since we want the minimum cost solution.
    pq = [(passingFees[0], 0, 0)]
    
    while pq:
        cost, time, city = heapq.heappop(pq)
        
        # If we have reached the destination, return the cost.
        if city == n - 1:
            return cost
        
        # If this cost is not the best known for (city, time), then skip it
        if cost > dp[city][time]:
            continue
        
        # Explore all the adjacent cities
        for neighbor, travel_time in graph[city]:
            new_time = time + travel_time
            # Only proceed if the new time does not exceed maxTime
            if new_time <= maxTime:
                new_cost = cost + passingFees[neighbor]
                # If a better (cheaper) cost for (neighbor, new_time) is found, update and push to the queue.
                if new_cost < dp[neighbor][new_time]:
                    dp[neighbor][new_time] = new_cost
                    heapq.heappush(pq, (new_cost, new_time, neighbor))
    return -1

# Example test case:
if __name__ == '__main__':
    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]
    print(minCost(maxTime, edges, passingFees))  # Expected output: 11
← Back to All Questions