Minimum Cost to Reach City With Discounts

Medium Graphs Dijkstra Original on LeetCode

Reported atFlipkart

Minimum Cost to Reach City With Discounts is a medium graphs problem solved with the dijkstra pattern. The best approach, optimal (dijkstra on city + discounts-used states), runs in O((n + m) · d · log(m · d)) time and O((n + m) · d) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bellman-ford on city + discounts-used states) up.

Problem

There are n cities numbered 0 to n - 1. Each entry highways[i] = [a, b, toll] is a two-way road between cities a and b that costs toll to drive along.

You also hold discounts coupons. Using one coupon on a road lets you pay toll / 2 (rounded down) for that trip instead of the full toll. A coupon can be spent on at most one road, and at most one coupon can be used per road trip.

Return the minimum total cost to travel from city 0 to city n - 1, or -1 if city n - 1 cannot be reached.

Examples

Example 1

Input
n = 4, highways = [[0,1,10],[1,3,10],[0,2,3],[2,3,30]], discounts = 1
Output
15
Why
Go 0 → 1 → 3 and use the discount on either road: 10 + 5 = 15. Halving the 30 on the other route still costs 3 + 15 = 18.

Example 2

Input
n = 3, highways = [[0,1,7]], discounts = 2
Output
-1
Why
City 2 has no roads, so it cannot be reached.

Example 3

Input
n = 3, highways = [[0,1,9],[1,2,5],[0,2,20]], discounts = 0
Output
14
Why
With no discounts this is a plain shortest path: 9 + 5 beats 20.

Constraints

  • 2 <= n <= 1000
  • 1 <= highways.length <= 1000; highways[i] = [a, b, toll] with 0 <= a, b < n, a != b, 0 <= toll <= 10^5.
  • Roads are two-way and there is at most one road between any pair of cities.
  • 0 <= discounts <= 500

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
Brute force (Bellman-Ford on city + discounts-used states)O(n · d · m · d)O(n · d)
Optimal (Dijkstra on city + discounts-used states)O((n + m) · d · log(m · d))O((n + m) · d)

1Brute force (Bellman-Ford on city + discounts-used states)

TimeO(n · d · m · d)Up to n·(d + 1) passes (one per state on a shortest path), each touching m roads × (d + 1) discount counts.
SpaceO(n · d)The dist table has n × (d + 1) entries.

Keep dist[city][used], the cheapest known cost to stand in city having used used discounts. Repeatedly relax every road in both directions, with and without a discount, until nothing improves.

  1. dist[0][0] = 0, everything else infinity.
  2. Loop until a full pass changes nothing: for each road (u, v, toll), in both directions, and each used k with a finite dist[u][k], try dist[u][k] + toll into dist[v][k] and, if k < discounts, dist[u][k] + toll / 2 into dist[v][k + 1].
  3. Answer = min over k of dist[n - 1][k], or -1 if all are infinite.
class Solution {
    public int minimumCost(int n, int[][] highways, int discounts) {
        final int INF = Integer.MAX_VALUE / 2;
        int[][] dist = new int[n][discounts + 1];
        for (int[] row : dist) Arrays.fill(row, INF);
        dist[0][0] = 0;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int[] h : highways)
                for (int dir = 0; dir < 2; dir++) {
                    int u = dir == 0 ? h[0] : h[1], v = dir == 0 ? h[1] : h[0];
                    for (int k = 0; k <= discounts; k++) {
                        if (dist[u][k] >= INF) continue;
                        if (dist[u][k] + h[2] < dist[v][k]) { dist[v][k] = dist[u][k] + h[2]; changed = true; }
                        if (k < discounts && dist[u][k] + h[2] / 2 < dist[v][k + 1]) { dist[v][k + 1] = dist[u][k] + h[2] / 2; changed = true; }
                    }
                }
        }
        int best = INF;
        for (int k = 0; k <= discounts; k++) best = Math.min(best, dist[n - 1][k]);
        return best >= INF ? -1 : best;
    }
}

2Optimal (Dijkstra on city + discounts-used states)

TimeO((n + m) · d · log(m · d))There are n·(d + 1) states and 2m·(d + 1) × 2 state edges; each heap operation costs a log.
SpaceO((n + m) · d)The dist table plus the heap, which can hold one entry per relaxed state edge.

Treat each (city, used) pair as a node of a layered graph. A road is an edge inside a layer (full toll) and an edge to the next layer (half toll). All weights are non-negative, so Dijkstra finds the cheapest state for city n - 1; the first time it is popped is the answer.

  1. Build an adjacency list with both directions of every road.
  2. dist[city][used] = infinity; dist[0][0] = 0; push (0, city 0, used 0) on a min-heap.
  3. Pop the cheapest state; skip it if stale. If the city is n - 1, return its cost.
  4. For each road (v, toll): relax (v, used) with cost + toll, and if used < discounts relax (v, used + 1) with cost + toll / 2.
  5. If the heap empties, return -1.
class Solution {
    public int minimumCost(int n, int[][] highways, int discounts) {
        List<int[]>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] h : highways) {
            g[h[0]].add(new int[] { h[1], h[2] });
            g[h[1]].add(new int[] { h[0], h[2] });
        }
        int[][] dist = new int[n][discounts + 1];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.add(new int[] { 0, 0, 0 }); // cost, city, used
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0], u = cur[1], used = cur[2];
            if (cost > dist[u][used]) continue;
            if (u == n - 1) return cost;
            for (int[] e : g[u]) {
                int v = e[0], toll = e[1];
                if (cost + toll < dist[v][used]) {
                    dist[v][used] = cost + toll;
                    pq.add(new int[] { cost + toll, v, used });
                }
                if (used < discounts && cost + toll / 2 < dist[v][used + 1]) {
                    dist[v][used + 1] = cost + toll / 2;
                    pq.add(new int[] { cost + toll / 2, v, used + 1 });
                }
            }
        }
        return -1;
    }
}

Edge cases to test

  • Destination unreachable: return -1
  • discounts = 0: ordinary shortest path
  • More discounts than roads on the best path (extra discounts are simply unused)
  • Odd tolls: halving rounds down (7 → 3)
  • A longer route with one expensive road can win once that road is halved

Hints

Hint 1

The cheapest way to reach a city depends on how many discounts you have left. Make that part of the state.

Hint 2

State = (city, discounts used). From a state you can cross a road paying the full toll, or (if any discount is left) paying half and moving to used + 1.

Hint 3

All costs are non-negative, so Dijkstra on this layered graph works. The answer is the first time you pop city n - 1.

FAQ

What is the best time complexity for Minimum Cost to Reach City With Discounts?

Optimal (Dijkstra on city + discounts-used states) runs in O((n + m) · d · log(m · d)) time and O((n + m) · d) extra space. There are n·(d + 1) states and 2m·(d + 1) × 2 state edges; each heap operation costs a log.

Which pattern does Minimum Cost to Reach City With Discounts use?

It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance, Cheapest Flights Within K Stops.

Is there a brute force solution for Minimum Cost to Reach City With Discounts?

Yes. Brute force (Bellman-Ford on city + discounts-used states) takes O(n · d · m · d) time and O(n · d) space. Keep dist[city][used], the cheapest known cost to stand in city having used used discounts.

Which edge cases should I test for Minimum Cost to Reach City With Discounts?

Destination unreachable: return -1; discounts = 0: ordinary shortest path; More discounts than roads on the best path (extra discounts are simply unused); Odd tolls: halving rounds down (7 → 3); A longer route with one expensive road can win once that road is halved.