HardArrayDynamic ProgrammingGraphDijkstra's AlgorithmUpdated Sep 2026

1928. Minimum Cost to Reach Destination in Time

Asked at Databricks

Difficulty

Hard

Time

O(E * maxTime * log(n * maxTime)

Space

O(n * maxTime)

Pattern

Array

Companies

1

Problem

You are given a country with n cities, numbered 0 to n - 1, joined by bi-directional roads. Each road is given as edges[i] = [x, y, time], meaning you can travel between city x and city y in time minutes. Two cities may be joined by several roads with different travel times.

Every time you enter a city you must pay a fee. The array passingFees gives the fee for each city: passingFees[j] is the money you pay when you pass through city j. You pay for the start city and the destination city too.

You start at city 0 and want to reach city n - 1 using at most maxTime minutes in total. Return the minimum total fee of a trip that finishes in time, or -1 if no such trip exists.

Two things to balance: time and money

0 → 1 (10 min, $5+$1)1 → 2 (10 min, +$2)2 → 5 (10 min, +$3)total 30 min, $11The cheapest route is also the slowest one here.
The cheap route 0 → 1 → 2 → 5 costs 11 but needs 30 minutes, so it only works when maxTime is at least 30.

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.

Examples

Example 1
InputmaxTime = 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]
Output11
WhyThe route 0 → 1 → 2 → 5 uses 10 + 10 + 10 = 30 minutes, which fits exactly. Its fees are 5 + 1 + 2 + 3 = 11, the cheapest possible.
Example 2
InputmaxTime = 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]
Output48
WhyThe 30-minute route is now too slow. The only route that fits is 0 → 3 → 4 → 5, taking 1 + 10 + 15 = 26 minutes, with fees 5 + 20 + 20 + 3 = 48.
Example 3
InputmaxTime = 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
WhyThe fastest route takes 26 minutes, which is more than 25, so city 5 cannot be reached in time.

Asked At

1 companies
CompanyDifficulty
DatabricksHardView all Databricks questions →

How to Think About It

1

Brute force: enumerate all paths from node 0 to node n-1, check if each fits within the time constraint, and track minimum cost.

2

Notice that both time and money are constraints. A state must capture (node, time_used) to decide cost.

3

Use Dijkstra-like BFS where the priority is cost, and the state is (cost, node, time_used).

4

At each state, explore all outgoing edges. If moving to a neighbor stays within the time limit and offers a cheaper cost for that (node, time) pair, push it into the priority queue.

5

Maintain a 2D array dist[node][time] storing the minimum cost to reach each node at each time. The answer is the minimum of dist[n-1][t] for all t <= timeLimit.

Optimal Approach

Model the problem as a shortest path in a state space where each state is (node, time_used). Use a priority queue sorted by cost. For each state, explore all outgoing edges. If moving to a neighbor via an edge with cost c and travel time t_new stays within the time limit and improves dist[neighbor][time_used + t_new], update and push. The answer is the minimum cost across all time slots at node n-1. This is essentially Dijkstra on an expanded graph where time is an additional dimension.

Dijkstra over (city, time) states

dist[city][time]010202629300120∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞Start: city 0 at time 0 costs $0; everything else isunknowndist[city][time]010202629300120∞∞∞∞∞∞6∞∞∞∞∞∞8∞∞∞Pop (cost 5, city 0, time 0), then relax: city 1 att=10 costs 6, city 2 at t=20 costs 8dist[city][time]010202629300120∞∞∞∞∞∞6∞∞∞∞∞∞8∞∞∞Reaching city 5 at t=30 costs 11 — the first time wepop city 5, that cost is the answerstate = (cost, city, time_used)relax edge if time_used + w <= maxTimeanswer = first cost popped at city n-1
We expand states in order of money spent, and only keep a state if it is cheaper than any earlier way to reach that city at that time.
ComplexityTime O(E * maxTime * log(n * maxTime)Space O(n * maxTime)There are n * maxTime possible states, and each popped state scans its outgoing edges; the log factor comes from the priority queue.

What Trips People Up in Real Interviews

1

Clarify whether the graph can have negative costs (usually no). Ask about the range of timeLimit and n.

2

State the brute force approach first, then explain why DP or Dijkstra is needed.

3

Explain the state definition clearly: dist[node][time] = minimum cost.

4

Walk through a small example step by step before coding.

5

Discuss the time complexity: O(timeLimit * (n + m) * log(timeLimit * n)).

Solution Code

O(E * maxTime * log(n * maxTime) time
import heapq

def minCostToReachDestination(n, edges, timeLimit, maxCost):
    graph = [[] for _ in range(n)]
    for u, v, cost, time in edges:
        graph[u].append((v, cost, time))
    INF = float('inf')
    dist = [[INF] * (timeLimit + 1) for _ in range(n)]
    dist[0][0] = 0
    pq = [(0, 0, 0)]
    while pq:
        d, u, t = heapq.heappop(pq)
        if d > dist[u][t]:
            continue
        if u == n - 1:
            return d
        for v, cost, travel_time in graph[u]:
            nt = t + travel_time
            if nt <= timeLimit and d + cost < dist[v][nt]:
                dist[v][nt] = d + cost
                heapq.heappush(pq, (d + cost, v, nt))
    return -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Cost to Reach Destination in Time problem?

You are given a weighted directed graph with n nodes and m edges. Each edge has a travel time and a cost. You start at node 0 with a certain amount of money and must reach node n-1 within a given time limit. Find the minimum cost to reach the destination, or return -1 if impossible.

How do you solve Minimum Cost to Reach Destination in Time?

The optimal approach runs in O(E * maxTime * log(n * maxTime) time and O(n * maxTime) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Cost to Reach Destination in Time?

Minimum Cost to Reach Destination in Time is asked at Databricks. It is a hard difficulty problem.

What are common mistakes on Minimum Cost to Reach Destination in Time?
  • Clarify whether the graph can have negative costs (usually no). Ask about the range of timeLimit and n.
  • State the brute force approach first, then explain why DP or Dijkstra is needed.
  • Explain the state definition clearly: dist[node][time] = minimum cost.
  • Walk through a small example step by step before coding.
  • Discuss the time complexity: O(timeLimit * (n + m) * log(timeLimit * n)).