Minimum Cost to Reach Destination in Time: DP on Graphs

You are given n cities numbered 0 to n-1, a list of edges where each edge connects two cities with a travel time, an array of passing fees (one per city), and a maxTime budget. Find the minimum total cost (sum of passing fees for every city you visit, including the start and the destination) to travel from city 0 to city n-1 without exceeding maxTime. If it is impossible to arrive in time, return -1.

This is LeetCode 1928: Minimum Cost to Reach Destination in Time, and it is a textbook example of constrained shortest path. You cannot just minimize cost greedily, because the cheapest route might be too slow. You cannot just minimize time, because the fastest route might be too expensive. You need to track both dimensions simultaneously.

Why this problem matters

Most graph shortest-path problems optimize a single dimension: shortest distance, fewest edges, or minimum weight. This problem has two competing objectives, cost and time, with a hard constraint on one of them. That makes it a constrained optimization problem on a graph.

The pattern shows up in real-world routing (cheapest flight within a time window), network design (minimum cost path with bandwidth constraints), and resource-constrained scheduling. In interview settings, it tests whether you can extend standard graph algorithms by adding a second dimension to the DP state.

If you have solved Coin Change or Dungeon Game, you already know how to reason about DP with constraints. This problem applies the same thinking to a graph structure instead of a linear array or grid.

The approach: DP with time as state

The key idea is to define dp[node][t] as the minimum cost to reach node using exactly t time units. You then relax edges in a way that fills this 2D table.

Initialize dp[0][0] = passingFees[0] (starting at city 0 at time 0 costs the fee for city 0). Everything else starts at infinity.

For each state (city, t) with a known cost, try every edge (city, neighbor, edgeTime). If t + edgeTime is within maxTime and dp[city][t] + passingFees[neighbor] improves dp[neighbor][t + edgeTime], update it.

The answer is min(dp[n-1][t]) for all t from 0 to maxTime. If no such state was reached, return -1.

def min_cost(max_time, edges, passing_fees):
    n = len(passing_fees)
    INF = float("inf")
    dp = [[INF] * (max_time + 1) for _ in range(n)]
    dp[0][0] = passing_fees[0]

    graph = [[] for _ in range(n)]
    for x, y, t in edges:
        graph[x].append((y, t))
        graph[y].append((x, t))

    for t in range(max_time + 1):
        for city in range(n):
            if dp[city][t] == INF:
                continue
            for neighbor, travel_time in graph[city]:
                new_time = t + travel_time
                if new_time > max_time:
                    continue
                new_cost = dp[city][t] + passing_fees[neighbor]
                if new_cost < dp[neighbor][new_time]:
                    dp[neighbor][new_time] = new_cost

    ans = min(dp[n - 1])
    return ans if ans < INF else -1

Visual walkthrough

Let's trace the algorithm on a small graph with 4 cities: fees = [5, 20, 10, 8], maxTime = 30, and five edges connecting them. Watch how the DP explores states and discovers that the cheapest path is not the fastest one.

The cheapest path 0 -> 2 -> 3 costs 23 in fees but uses 25 time units. The fastest path 0 -> 1 -> 3 only uses 20 time units but costs 33. Because we are optimizing for cost (not speed), the slower and cheaper route wins, as long as it fits within maxTime.

Alternative: Dijkstra with (cost, time, city) states

You can also solve this with a priority queue (min-heap) ordered by cost. Push (passingFees[0], 0, 0) as the starting state. For each popped state, try all edges and push new states if the time constraint is satisfied and the new cost improves on the best known cost for that (city, time) pair.

import heapq

def min_cost_dijkstra(max_time, edges, passing_fees):
    n = len(passing_fees)
    INF = float("inf")
    best = [[INF] * (max_time + 1) for _ in range(n)]
    best[0][0] = passing_fees[0]

    graph = [[] for _ in range(n)]
    for x, y, t in edges:
        graph[x].append((y, t))
        graph[y].append((x, t))

    heap = [(passing_fees[0], 0, 0)]

    while heap:
        cost, time_used, city = heapq.heappop(heap)
        if city == n - 1:
            return cost
        if cost > best[city][time_used]:
            continue
        for neighbor, travel_time in graph[city]:
            new_time = time_used + travel_time
            if new_time > max_time:
                continue
            new_cost = cost + passing_fees[neighbor]
            if new_cost < best[neighbor][new_time]:
                best[neighbor][new_time] = new_cost
                heapq.heappush(heap, (new_cost, new_time, neighbor))

    return -1

Complexity analysis

n is the number of cities, E is the number of edges, and maxTime is the time budget.

Time (DP): We iterate over all time values (0 to maxTime) and for each, process all edges. Each edge is checked at most maxTime times.

Space: Both approaches store a 2D table of size n * (maxTime + 1). The Dijkstra variant also uses a heap that can grow up to O(n * maxTime) entries in the worst case.

Edge cases to watch for

• No path exists: cities 0 and n-1 are in disconnected components. Every entry in dp[n-1] stays at infinity. Return -1.
• Only one city: n = 1, city 0 is also the destination. Return passingFees[0] immediately.
• maxTime = 0: you can only stay at city 0. If n = 1, return passingFees[0]. Otherwise return -1.
• Multiple edges between same cities: the graph can have parallel edges with different travel times. Process all of them.
• Very tight time budget: the only feasible path might be the direct edge (if one exists). The DP handles this naturally since shorter-time paths are explored first.
• All paths cost the same: when fees are identical, the problem degenerates to finding any path within the time budget.

The building blocks

This problem combines two foundational patterns:

1. DP with an extra dimension

Standard shortest path uses dp[node]. Adding a constraint (time, fuel, stops) introduces a second dimension: dp[node][resource]. You have seen this pattern in problems like Cheapest Flights Within K Stops where the extra dimension is the number of stops remaining.

The technique generalizes to any graph problem where you optimize one metric subject to a constraint on another. Define the DP state to include both the position and the constrained resource. Iterate through the resource dimension in order so that transitions are well-defined.

2. Constrained shortest path on graphs

In unconstrained shortest path (Dijkstra, Bellman-Ford), each node has one "best" value. With a constraint, the same node can have many valid states, one for each feasible value of the constrained resource. You cannot prune a state just because its cost is not globally optimal. A state with higher cost but lower time usage might lead to a better solution downstream.

This is why the 2D table is necessary. You are essentially running shortest path on an expanded graph where each original node is split into multiple copies, one per feasible time value.

From understanding to recall

You now see how to add a time dimension to a shortest-path DP, how to iterate through states in time order, and why the 2D table prevents premature pruning. The logic makes sense when you read it. But writing it from scratch under interview pressure is a different challenge.

The tricky parts are initializing the DP correctly (do not forget the starting fee), iterating in the right order (time must increase), and remembering to check all time values at the destination to find the global minimum. These details are easy to get wrong when you are nervous.

Spaced repetition turns this from "I understand the concept" into "I can write it cold." You practice the DP formulation, the edge relaxation loop, and the final answer extraction at increasing intervals until they become automatic. When a constrained graph optimization problem appears in your interview, you do not re-derive the approach. You just write it.

Related posts

• Coin Change - Classic DP with optimal substructure
• Clone Graph - Graph traversal fundamentals
• Course Schedule - Graph traversal with constraints