Minimum Cost to Reach City With Discounts
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 <= 10001 <= highways.length <= 1000;highways[i] = [a, b, toll]with0 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(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.O(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.
- dist[0][0] = 0, everything else infinity.
- 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].
- 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;
}
}class Solution:
def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
INF = float('inf')
dist = [[INF] * (discounts + 1) for _ in range(n)]
dist[0][0] = 0
changed = True
while changed:
changed = False
for a, b, toll in highways:
for u, v in ((a, b), (b, a)):
du, dv = dist[u], dist[v]
for k in range(discounts + 1):
if du[k] == INF:
continue
if du[k] + toll < dv[k]:
dv[k] = du[k] + toll
changed = True
if k < discounts and du[k] + toll // 2 < dv[k + 1]:
dv[k + 1] = du[k] + toll // 2
changed = True
best = min(dist[n - 1])
return -1 if best == INF else bestclass Solution {
public:
int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
const int INF = INT_MAX / 2;
vector<vector<int>> dist(n, vector<int>(discounts + 1, INF));
dist[0][0] = 0;
bool changed = true;
while (changed) {
changed = false;
for (auto& 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 = min(best, dist[n - 1][k]);
return best >= INF ? -1 : best;
}
};function minimumCost(n, highways, discounts) {
const dist = Array.from({ length: n }, () => new Array(discounts + 1).fill(Infinity));
dist[0][0] = 0;
let changed = true;
while (changed) {
changed = false;
for (const h of highways)
for (let dir = 0; dir < 2; dir++) {
const u = dir === 0 ? h[0] : h[1], v = dir === 0 ? h[1] : h[0];
for (let k = 0; k <= discounts; k++) {
if (dist[u][k] === Infinity) continue;
if (dist[u][k] + h[2] < dist[v][k]) { dist[v][k] = dist[u][k] + h[2]; changed = true; }
const half = Math.floor(h[2] / 2);
if (k < discounts && dist[u][k] + half < dist[v][k + 1]) { dist[v][k + 1] = dist[u][k] + half; changed = true; }
}
}
}
const best = Math.min(...dist[n - 1]);
return best === Infinity ? -1 : best;
}2Optimal (Dijkstra on city + discounts-used states)
O((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.O((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.
- Build an adjacency list with both directions of every road.
- dist[city][used] = infinity; dist[0][0] = 0; push (0, city 0, used 0) on a min-heap.
- Pop the cheapest state; skip it if stale. If the city is n - 1, return its cost.
- For each road (v, toll): relax (v, used) with cost + toll, and if used < discounts relax (v, used + 1) with cost + toll / 2.
- 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;
}
}class Solution:
def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
g = [[] for _ in range(n)]
for a, b, toll in highways:
g[a].append((b, toll))
g[b].append((a, toll))
INF = float('inf')
dist = [[INF] * (discounts + 1) for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)] # cost, city, used
while pq:
cost, u, used = heapq.heappop(pq)
if cost > dist[u][used]:
continue
if u == n - 1:
return cost
for v, toll in g[u]:
if cost + toll < dist[v][used]:
dist[v][used] = cost + toll
heapq.heappush(pq, (cost + toll, v, used))
if used < discounts and cost + toll // 2 < dist[v][used + 1]:
dist[v][used + 1] = cost + toll // 2
heapq.heappush(pq, (cost + toll // 2, v, used + 1))
return -1class 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<int>> dist(n, vector<int>(discounts + 1, INT_MAX));
dist[0][0] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
pq.push({0, 0, 0}); // cost, city, used
while (!pq.empty()) {
auto [cost, u, used] = pq.top();
pq.pop();
if (cost > dist[u][used]) continue;
if (u == n - 1) return cost;
for (auto [v, toll] : g[u]) {
if (cost + toll < dist[v][used]) {
dist[v][used] = cost + toll;
pq.push({cost + toll, v, used});
}
if (used < discounts && cost + toll / 2 < dist[v][used + 1]) {
dist[v][used + 1] = cost + toll / 2;
pq.push({cost + toll / 2, v, used + 1});
}
}
}
return -1;
}
};function minimumCost(n, highways, discounts) {
const g = Array.from({ length: n }, () => []);
for (const [a, b, toll] of highways) {
g[a].push([b, toll]);
g[b].push([a, toll]);
}
const dist = Array.from({ length: n }, () => new Array(discounts + 1).fill(Infinity));
dist[0][0] = 0;
const pq = [];
const push = (x) => {
pq.push(x);
let i = pq.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (pq[p][0] <= pq[i][0]) break;
[pq[p], pq[i]] = [pq[i], pq[p]];
i = p;
}
};
const pop = () => {
const top = pq[0];
const last = pq.pop();
if (pq.length > 0) {
pq[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < pq.length && pq[l][0] < pq[m][0]) m = l;
if (r < pq.length && pq[r][0] < pq[m][0]) m = r;
if (m === i) break;
[pq[m], pq[i]] = [pq[i], pq[m]];
i = m;
}
}
return top;
};
push([0, 0, 0]); // cost, city, used
while (pq.length > 0) {
const [cost, u, used] = pop();
if (cost > dist[u][used]) continue;
if (u === n - 1) return cost;
for (const [v, toll] of g[u]) {
if (cost + toll < dist[v][used]) {
dist[v][used] = cost + toll;
push([cost + toll, v, used]);
}
const half = Math.floor(toll / 2);
if (used < discounts && cost + half < dist[v][used + 1]) {
dist[v][used + 1] = cost + half;
push([cost + half, 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.