Minimum Cost to Reach Destination in Time - Solution & Explanation

Problem Overview: You are given a graph where each city has a passing fee and each road has a travel time. Starting from city 0, reach city n-1 without exceeding maxTime. The goal is to minimize the total cost (sum of passing fees). If the destination cannot be reached within the allowed time, return -1.

This is a constrained shortest path problem. Traditional shortest path algorithms minimize either distance or cost, but here you must minimize cost while keeping total travel time ≤ maxTime. That constraint turns the problem into a hybrid of graph traversal and dynamic programming.

Approach 1: Dijkstra's Algorithm with Time Constraint (Time: O(E log V), Space: O(V * maxTime))

Treat each state as (city, timeSpent). Instead of tracking only the shortest distance, maintain the minimum cost required to reach a city at a specific time. Use a priority queue ordered by cost. From the current state, iterate over neighboring cities and push a new state if the updated time does not exceed maxTime. Maintain a DP table cost[city][time] to avoid revisiting worse states. This approach works because Dijkstra always expands the lowest-cost state first, ensuring that once the destination is reached within the allowed time, the cost is minimal. It performs well when the graph is sparse and is usually the fastest solution in practice.

Approach 2: Bellman-Ford Style Dynamic Programming (Time: O(maxTime * E), Space: O(V))

Another way is to iterate over time like a dynamic programming dimension. Maintain an array where dp[i] stores the minimum cost to reach city i. For each time unit up to maxTime, relax all edges. When relaxing an edge (u → v) with travel time t, update the cost for reaching v if the total time stays within the limit. To avoid overwriting values in the same iteration, copy the previous DP state before relaxing edges. This approach resembles the Bellman-Ford algorithm applied across time layers and works well for dense graphs. It explicitly explores all feasible transitions without using a priority queue.

Both solutions rely on modeling the graph using adjacency lists built from the input arrays. The key insight is that the same city can be visited multiple times if the arrival time differs, because a later arrival might still produce a cheaper total cost.

Recommended for interviews: Dijkstra with a time constraint is the preferred solution. Interviewers expect you to recognize this as a shortest-path problem with an additional state dimension. The Bellman-Ford style DP demonstrates strong understanding of relaxation techniques and constrained path problems, but the priority-queue solution is usually considered the optimal and most scalable approach.