Problem

A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.

You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once , and you can only use at most one discount per highway.

Return _theminimum total cost to go from city _0 to cityn - 1 , or-1 if it is not possible to go from city0 to cityn - 1 .

Examples

Example 1:

1
2
3
4
5
6
7

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2000-2099/2093.Minimum%20Cost%20to%20Reach%20City%20With%20Discounts/images/image-20211129222429-1.png)
Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], discounts = 1
Output: 9
Explanation:
Go from 0 to 1 for a cost of 4.
Go from 1 to 4 and use a discount for a cost of 11 / 2 = 5.
The minimum cost to go from 0 to 4 is 4 + 5 = 9.

Example 2:

1
2
3
4
5
6
7
8

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2000-2099/2093.Minimum%20Cost%20to%20Reach%20City%20With%20Discounts/images/image-20211129222650-4.png)
Input: n = 4, highways = [[1,3,17],[1,2,7],[3,2,5],[0,1,6],[3,0,20]], discounts = 20
Output: 8
Explanation:
Go from 0 to 1 and use a discount for a cost of 6 / 2 = 3.
Go from 1 to 2 and use a discount for a cost of 7 / 2 = 3.
Go from 2 to 3 and use a discount for a cost of 5 / 2 = 2.
The minimum cost to go from 0 to 3 is 3 + 3 + 2 = 8.

Example 3:

1
2
3
4
5

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2000-2099/2093.Minimum%20Cost%20to%20Reach%20City%20With%20Discounts/images/image-20211129222531-3.png)
Input: n = 4, highways = [[0,1,3],[2,3,2]], discounts = 0
Output: -1
Explanation:
It is impossible to go from 0 to 3 so return -1.

Constraints:

  • 2 <= n <= 1000
  • 1 <= highways.length <= 1000
  • highways[i].length == 3
  • 0 <= city1i, city2i <= n - 1
  • city1i != city2i
  • 0 <= tolli <= 10^5
  • 0 <= discounts <= 500
  • There are no duplicate highways.

Solution

Method 1 – Dijkstra’s Algorithm with State (Discounts Used)

Intuition

We need to find the minimum cost from city 0 to city n-1, using up to discounts discounts, where each discount halves the toll on a highway. This is a shortest path problem with an extra state: the number of discounts used so far. Dijkstra’s algorithm can be adapted to handle this state.

Approach

  1. Build the graph from the highways list.
  2. Use Dijkstra’s algorithm, where each state is (city, discounts_used).
  3. For each edge, try both options:
    • Travel without discount (pay full toll).
    • If discounts remain, travel with discount (pay toll // 2).
  4. Track the minimum cost to reach each (city, discounts_used).
  5. The answer is the minimum cost to reach city n-1 with any number of discounts used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
        vector<vector<pair<int,int>>> g(n);
        for (auto& h : highways) {
            g[h[0]].push_back({h[1], h[2]});
            g[h[1]].push_back({h[0], h[2]});
        }
        vector<vector<long long>> dist(n, vector<long long>(discounts+1, LLONG_MAX));
        priority_queue<tuple<long long,int,int>, vector<tuple<long long,int,int>>, greater<>> pq;
        dist[0][0] = 0;
        pq.push({0, 0, 0});
        while (!pq.empty()) {
            auto [cost, u, d] = pq.top(); pq.pop();
            if (cost > dist[u][d]) continue;
            for (auto& [v, w] : g[u]) {
                if (dist[v][d] > cost + w) {
                    dist[v][d] = cost + w;
                    pq.push({dist[v][d], v, d});
                }
                if (d < discounts && dist[v][d+1] > cost + w/2) {
                    dist[v][d+1] = cost + w/2;
                    pq.push({dist[v][d+1], v, d+1});
                }
            }
        }
        long long ans = LLONG_MAX;
        for (int d = 0; d <= discounts; ++d) ans = min(ans, dist[n-1][d]);
        return ans == LLONG_MAX ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func minimumCost(n int, highways [][]int, discounts int) int {
    g := make([][][2]int, n)
    for _, h := range highways {
        g[h[0]] = append(g[h[0]], [2]int{h[1], h[2]})
        g[h[1]] = append(g[h[1]], [2]int{h[0], h[2]})
    }
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, discounts+1)
        for j := range dist[i] { dist[i][j] = 1<<62 }
    }
    dist[0][0] = 0
    pq := &heapMin{}; heap.Init(pq)
    heap.Push(pq, node{0, 0, 0})
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(node)
        if cur.c > dist[cur.u][cur.d] { continue }
        for _, e := range g[cur.u] {
            v, w := e[0], e[1]
            if dist[v][cur.d] > cur.c+w {
                dist[v][cur.d] = cur.c+w
                heap.Push(pq, node{dist[v][cur.d], v, cur.d})
            }
            if cur.d < discounts && dist[v][cur.d+1] > cur.c+w/2 {
                dist[v][cur.d+1] = cur.c+w/2
                heap.Push(pq, node{dist[v][cur.d+1], v, cur.d+1})
            }
        }
    }
    ans := 1<<62
    for d := 0; d <= discounts; d++ {
        if dist[n-1][d] < ans { ans = dist[n-1][d] }
    }
    if ans == 1<<62 { return -1 } else { return ans }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int minimumCost(int n, int[][] highways, int discounts) {
        List<int[]>[] g = new ArrayList[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]});
        }
        long[][] dist = new long[n][discounts+1];
        for (long[] row : dist) Arrays.fill(row, Long.MAX_VALUE);
        dist[0][0] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a->a[0]));
        pq.offer(new long[]{0, 0, 0});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long cost = cur[0]; int u = (int)cur[1], d = (int)cur[2];
            if (cost > dist[u][d]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (dist[v][d] > cost + w) {
                    dist[v][d] = cost + w;
                    pq.offer(new long[]{dist[v][d], v, d});
                }
                if (d < discounts && dist[v][d+1] > cost + w/2) {
                    dist[v][d+1] = cost + w/2;
                    pq.offer(new long[]{dist[v][d+1], v, d+1});
                }
            }
        }
        long ans = Long.MAX_VALUE;
        for (int d = 0; d <= discounts; ++d) ans = Math.min(ans, dist[n-1][d]);
        return ans == Long.MAX_VALUE ? -1 : (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun minimumCost(n: Int, highways: Array<IntArray>, discounts: Int): Int {
        val g = Array(n) { mutableListOf<Pair<Int,Int>>() }
        for (h in highways) {
            g[h[0]].add(Pair(h[1], h[2]))
            g[h[1]].add(Pair(h[0], h[2]))
        }
        val dist = Array(n) { LongArray(discounts+1) { Long.MAX_VALUE } }
        dist[0][0] = 0L
        val pq = PriorityQueue(compareBy<Pair<Long, Pair<Int,Int>>> { it.first })
        pq.add(Pair(0L, Pair(0,0)))
        while (pq.isNotEmpty()) {
            val (cost, p) = pq.poll()
            val (u, d) = p
            if (cost > dist[u][d]) continue
            for ((v, w) in g[u]) {
                if (dist[v][d] > cost + w) {
                    dist[v][d] = cost + w
                    pq.add(Pair(dist[v][d], Pair(v, d)))
                }
                if (d < discounts && dist[v][d+1] > cost + w/2) {
                    dist[v][d+1] = cost + w/2
                    pq.add(Pair(dist[v][d+1], Pair(v, d+1)))
                }
            }
        }
        var ans = Long.MAX_VALUE
        for (d in 0..discounts) ans = minOf(ans, dist[n-1][d])
        return if (ans == Long.MAX_VALUE) -1 else ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumCost(self, n: int, highways: list[list[int]], discounts: int) -> int:
        import heapq
        g = [[] for _ in range(n)]
        for a, b, w in highways:
            g[a].append((b, w))
            g[b].append((a, w))
        dist = [[float('inf')] * (discounts+1) for _ in range(n)]
        dist[0][0] = 0
        pq: list[tuple[int, int, int]] = [(0, 0, 0)]
        while pq:
            cost, u, d = heapq.heappop(pq)
            if cost > dist[u][d]: continue
            for v, w in g[u]:
                if dist[v][d] > cost + w:
                    dist[v][d] = cost + w
                    heapq.heappush(pq, (dist[v][d], v, d))
                if d < discounts and dist[v][d+1] > cost + w//2:
                    dist[v][d+1] = cost + w//2
                    heapq.heappush(pq, (dist[v][d+1], v, d+1))
        ans = min(dist[n-1])
        return -1 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn minimum_cost(n: i32, highways: Vec<Vec<i32>>, discounts: i32) -> i32 {
        use std::collections::BinaryHeap;
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for h in &highways {
            g[h[0] as usize].push((h[1] as usize, h[2]));
            g[h[1] as usize].push((h[0] as usize, h[2]));
        }
        let mut dist = vec![vec![i64::MAX; (discounts+1) as usize]; n];
        dist[0][0] = 0;
        let mut pq = BinaryHeap::new();
        pq.push(std::cmp::Reverse((0, 0, 0)));
        while let Some(std::cmp::Reverse((cost, u, d))) = pq.pop() {
            if cost > dist[u][d] { continue; }
            for &(v, w) in &g[u] {
                if dist[v][d] > cost + w as i64 {
                    dist[v][d] = cost + w as i64;
                    pq.push(std::cmp::Reverse((dist[v][d], v, d)));
                }
                if d < discounts as usize && dist[v][d+1] > cost + (w/2) as i64 {
                    dist[v][d+1] = cost + (w/2) as i64;
                    pq.push(std::cmp::Reverse((dist[v][d+1], v, d+1)));
                }
            }
        }
        let ans = *dist[n-1].iter().min().unwrap();
        if ans == i64::MAX { -1 } else { ans as i32 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    minimumCost(n: number, highways: number[][], discounts: number): number {
        const g: [number, number][][] = Array.from({length: n}, () => []);
        for (const [a, b, w] of highways) {
            g[a].push([b, w]);
            g[b].push([a, w]);
        }
        const dist: number[][] = Array.from({length: n}, () => Array(discounts+1).fill(Infinity));
        dist[0][0] = 0;
        const pq: [number, number, number][] = [[0, 0, 0]];
        while (pq.length) {
            pq.sort((a, b) => a[0] - b[0]);
            const [cost, u, d] = pq.shift()!;
            if (cost > dist[u][d]) continue;
            for (const [v, w] of g[u]) {
                if (dist[v][d] > cost + w) {
                    dist[v][d] = cost + w;
                    pq.push([dist[v][d], v, d]);
                }
                if (d < discounts && dist[v][d+1] > cost + Math.floor(w/2)) {
                    dist[v][d+1] = cost + Math.floor(w/2);
                    pq.push([dist[v][d+1], v, d+1]);
                }
            }
        }
        const ans = Math.min(...dist[n-1]);
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * discounts * log(n * discounts)) where m is the number of highways and n is the number of cities.
  • 🧺 Space complexity: O(n * discounts) for the distance table.