Minimum Cost to Reach Destination in Time

Hard Dynamic Programming 2D DP Original on LeetCode

Minimum Cost to Reach Destination in Time is a hard dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (dp over elapsed time), runs in O(maxTime · (n + E)) time and O(maxTime · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dijkstra on fees, pruned by arrival time up.

Problem

A country has n cities numbered 0 to n - 1, linked by two-way roads. edges[i] = [x, y, time] is a road between cities x and y that takes time minutes to drive. Two cities may be linked by more than one road.

Every time you are in city j (including the start and the end of the trip) you pay its fee passingFees[j]. You start in city 0 and want to reach city n - 1 within at most maxTime minutes. Return the minimum total fee of such a trip, or -1 if city n - 1 cannot be reached in time.

Examples

Example 1

Input
maxTime = 20, edges = [[0, 1, 10], [1, 3, 10], [0, 2, 5], [2, 3, 5]], passingFees = [4, 2, 9, 3]
Output
9
Why
0 → 1 → 3 takes 20 minutes and costs 4 + 2 + 3 = 9, cheaper than 0 → 2 → 3 which costs 16.

Example 2

Input
maxTime = 15, edges = [[0, 1, 10], [1, 3, 10], [0, 2, 5], [2, 3, 5]], passingFees = [4, 2, 9, 3]
Output
16
Why
The cheap route now takes too long; 0 → 2 → 3 takes 10 minutes and costs 4 + 9 + 3 = 16.

Example 3

Input
maxTime = 4, edges = [[0, 1, 3], [1, 2, 3]], passingFees = [1, 1, 1]
Output
-1
Why
The only route takes 6 minutes.

Constraints

  • 1 <= maxTime <= 1000
  • n == passingFees.length, 2 <= n <= 1000
  • n - 1 <= edges.length <= 1000
  • edges[i] = [x, y, time], 0 <= x, y < n, x != y, 1 <= time <= 1000
  • 1 <= passingFees[j] <= 1000
  • The graph is connected; there may be several roads between the same two cities.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Dijkstra on fees, pruned by arrival timeO(T · E · log(T · E))O(T · E)
Optimal (DP over elapsed time)O(maxTime · (n + E))O(maxTime · n)

1Dijkstra on fees, pruned by arrival time

TimeO(T · E · log(T · E))Each city can be settled up to maxTime times (with strictly decreasing times), and each settling relaxes its roads.
SpaceO(T · E)The heap can hold that many states in the worst case.

Run Dijkstra where the priority is the total fee and each state also carries the time used. States leave the heap in fee order, so once a city has been settled at time t, any later state at that city with time >= t is both pricier and slower and can be dropped. The first time the destination is popped, its fee is the answer.

  1. Push (fee[0], 0, city 0); bestTime[v] = infinity for all v.
  2. Pop the cheapest state (c, t, u). If u is the destination, return c. If t >= bestTime[u], skip it; otherwise bestTime[u] = t.
  3. For each road (u, v, w): if t + w <= maxTime and t + w < bestTime[v], push (c + fee[v], t + w, v).
  4. If the heap empties, return -1.
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[] { e[1], e[2] });
            adj.get(e[1]).add(new int[] { e[0], e[2] });
        }
        int[] bestTime = new int[n];
        Arrays.fill(bestTime, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        pq.offer(new int[] { passingFees[0], 0, 0 });
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int c = cur[0], t = cur[1], u = cur[2];
            if (u == n - 1) return c;
            if (t >= bestTime[u]) continue;
            bestTime[u] = t;
            for (int[] e : adj.get(u)) {
                int nt = t + e[1];
                if (nt <= maxTime && nt < bestTime[e[0]]) pq.offer(new int[] { c + passingFees[e[0]], nt, e[0] });
            }
        }
        return -1;
    }
}

2Optimal (DP over elapsed time)

TimeO(maxTime · (n + E))Each of the maxTime rows relaxes every road twice.
SpaceO(maxTime · n)The table has maxTime + 1 rows of n cities.

Let best[t][v] be the cheapest total fee for standing in city v after exactly t minutes. Every road (x, y, w) leads from time t - w to time t in either direction, so filling the table in increasing t only ever reads finished rows. The answer is the smallest best[t][n - 1] for t up to maxTime.

  1. best[0][0] = fee[0]; every other entry is infinity.
  2. For t = 1..maxTime and each road (x, y, w) with w <= t: best[t][y] = min(best[t][y], best[t - w][x] + fee[y]), and the same with x and y swapped.
  3. Return the minimum of best[t][n - 1], or -1 if it is still infinity.
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        final int INF = Integer.MAX_VALUE / 2;
        int[][] best = new int[maxTime + 1][n];
        for (int[] row : best) Arrays.fill(row, INF);
        best[0][0] = passingFees[0];
        for (int t = 1; t <= maxTime; t++) {
            for (int[] e : edges) {
                int x = e[0], y = e[1], w = e[2];
                if (w > t) continue;
                if (best[t - w][x] + passingFees[y] < best[t][y]) best[t][y] = best[t - w][x] + passingFees[y];
                if (best[t - w][y] + passingFees[x] < best[t][x]) best[t][x] = best[t - w][y] + passingFees[x];
            }
        }
        int ans = INF;
        for (int t = 0; t <= maxTime; t++) ans = Math.min(ans, best[t][n - 1]);
        return ans >= INF ? -1 : ans;
    }
}

Edge cases to test

  • No route fits in maxTime: return -1
  • The cheapest route is too slow, so a pricier but faster one wins
  • Parallel roads with different travel times
  • Revisiting a city costs its fee again, so it never helps

Hints

Hint 1

Plain shortest path on fees is not enough: the cheapest route may be too slow. Your state needs both the city and the time used.

Hint 2

With time capped at 1000, define best[t][v] = cheapest fee to stand in city v after exactly t minutes.

Hint 3

Fill best in increasing t: every road (x, y, w) moves from best[t - w][x] to best[t][y] and adds fee[y]. The answer is the minimum of best[t][n - 1] over all t.

FAQ

What is the best time complexity for Minimum Cost to Reach Destination in Time?

Optimal (DP over elapsed time) runs in O(maxTime · (n + E)) time and O(maxTime · n) extra space. Each of the maxTime rows relaxes every road twice.

Which pattern does Minimum Cost to Reach Destination in Time use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Minimum Cost to Reach Destination in Time?

Yes. Dijkstra on fees, pruned by arrival time takes O(T · E · log(T · E)) time and O(T · E) space. Run Dijkstra where the priority is the total fee and each state also carries the time used.

Which edge cases should I test for Minimum Cost to Reach Destination in Time?

No route fits in maxTime: return -1; The cheapest route is too slow, so a pricier but faster one wins; Parallel roads with different travel times; Revisiting a city costs its fee again, so it never helps.