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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Reach Destination in Time

Difficulty: Hard

Problem Description

In a country with n cities connected by bi-directional roads, you start at city 0 and aim to reach city n - 1 within a given maxTime. Each city has a passing fee, and the goal is to find the minimum total passing fee incurred while traveling within the time limit.

Key Insights

  • All cities are connected, ensuring a path exists between any two cities.
  • Multiple roads can connect the same pair of cities with different travel times.
  • The solution involves balancing the travel time and the passing fee to minimize costs while adhering to the time constraint.
  • A graph traversal algorithm like Dijkstra's can be adapted for this problem, where nodes represent cities and edges represent roads with weights as travel time.

Space and Time Complexity

Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (cities).
Space Complexity: O(V), for storing the priority queue and the cost array.

Solution

To solve the problem, we can use a modified Dijkstra's algorithm. The algorithm will keep track of the minimum cost to reach each city given the time constraint. We use a priority queue to explore the cities, prioritizing those with lower costs. Each city visit also updates the total time spent. If we exceed maxTime, that path is discarded. The goal is to return the minimum cost to reach the destination city n - 1.

Code Solutions

import heapq
from collections import defaultdict

def minCost(maxTime, edges, passingFees):
    graph = defaultdict(list)
    for u, v, time in edges:
        graph[u].append((v, time))
        graph[v].append((u, time))

    pq = [(passingFees[0], 0, 0)]  # (cost, city, time)
    costs = {0: (passingFees[0], 0)}  # city: (cost, time)

    while pq:
        cost, city, time = heapq.heappop(pq)

        if city == len(passingFees) - 1:
            return cost

        for neighbor, travel_time in graph[city]:
            new_time = time + travel_time
            new_cost = cost + passingFees[neighbor]

            if new_time <= maxTime:
                if neighbor not in costs or new_cost < costs[neighbor][0]:
                    costs[neighbor] = (new_cost, new_time)
                    heapq.heappush(pq, (new_cost, neighbor, new_time))

    return -1
← Back to All Questions