Minimum Cost to Reach City With Discounts
Problem
A country has n cities connected by bidirectional highways[i] = [city1, city2, toll]. You start in city 0 and want to reach city n − 1. You have a number of discounts; each discount lets you take one highway for half its toll (rounded down). Each discount may be used on at most one highway, and each highway may carry at most one discount. Return the minimum total cost to reach city n − 1, or -1 if it cannot be reached.
The twist is that the cheapest route depends on how many discounts you have left, so the search state is the pair (city, discounts used). We run Dijkstra over this expanded graph: from a state, each highway branches into a full-toll move (same discount count) and, if discounts remain, a half-toll move (one more used).
n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], discounts = 19import heapq
def minimum_cost(n, highways, discounts):
adj = {i: [] for i in range(n)}
for u, v, t in highways:
adj[u].append((v, t))
adj[v].append((u, t))
INF = float('inf')
dist = [[INF] * (discounts + 1) for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
while pq:
d, u, k = heapq.heappop(pq)
if d > dist[u][k]:
continue
for v, t in adj[u]:
if d + t < dist[v][k]:
dist[v][k] = d + t
heapq.heappush(pq, (d + t, v, k))
if k < discounts:
nd = d + t // 2
if nd < dist[v][k + 1]:
dist[v][k + 1] = nd
heapq.heappush(pq, (nd, v, k + 1))
ans = min(dist[n - 1])
return ans if ans < INF else -1function minimumCost(n, highways, discounts) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, t] of highways) {
adj[u].push([v, t]);
adj[v].push([u, t]);
}
const dist = Array.from({ length: n }, () => new Array(discounts + 1).fill(Infinity));
dist[0][0] = 0;
const pq = [[0, 0, 0]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u, k] = pq.shift();
if (d > dist[u][k]) continue;
for (const [v, t] of adj[u]) {
if (d + t < dist[v][k]) {
dist[v][k] = d + t;
pq.push([d + t, v, k]);
}
if (k < discounts) {
const nd = d + Math.floor(t / 2);
if (nd < dist[v][k + 1]) {
dist[v][k + 1] = nd;
pq.push([nd, v, k + 1]);
}
}
}
}
const ans = Math.min(...dist[n - 1]);
return ans === Infinity ? -1 : ans;
}class Solution {
public int minimumCost(int n, int[][] highways, int discounts) {
List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] h : highways) {
adj[h[0]].add(new int[]{h[1], h[2]});
adj[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) -> a[0] - b[0]);
pq.offer(new int[]{0, 0, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1], k = top[2];
if (d > dist[u][k]) continue;
for (int[] nb : adj[u]) {
int v = nb[0], t = nb[1];
if (d + t < dist[v][k]) {
dist[v][k] = d + t;
pq.offer(new int[]{d + t, v, k});
}
if (k < discounts && d + t / 2 < dist[v][k + 1]) {
dist[v][k + 1] = d + t / 2;
pq.offer(new int[]{d + t / 2, v, k + 1});
}
}
}
int ans = Integer.MAX_VALUE;
for (int k = 0; k <= discounts; k++) ans = Math.min(ans, dist[n - 1][k]);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}class Solution {
public:
int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
vector<vector<pair<int,int>>> adj(n);
for (auto& h : highways) {
adj[h[0]].push_back({h[1], h[2]});
adj[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<>> pq;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto [d, u, k] = pq.top(); pq.pop();
if (d > dist[u][k]) continue;
for (auto& [v, t] : adj[u]) {
if (d + t < dist[v][k]) {
dist[v][k] = d + t;
pq.push({d + t, v, k});
}
if (k < discounts && d + t / 2 < dist[v][k + 1]) {
dist[v][k + 1] = d + t / 2;
pq.push({d + t / 2, v, k + 1});
}
}
}
int ans = INT_MAX;
for (int k = 0; k <= discounts; k++) ans = min(ans, dist[n - 1][k]);
return ans == INT_MAX ? -1 : ans;
}
};Explanation
If there were no discounts this would be plain Dijkstra. Discounts complicate things because the best move out of a city now depends on how many discounts you still have — so we make the number of discounts used part of the state. A state is the pair (city, k) where k is discounts spent so far.
We keep dist[city][k], the cheapest cost to arrive at city having used exactly k discounts, all infinite except dist[0][0] = 0. A min-heap of (cost, city, k) always expands the cheapest unsettled state first, which keeps Dijkstra correct because all tolls are non-negative.
When we pop (d, u, k) we try every highway twice. The full-toll option goes to (v, k) for d + toll. The discounted option, available only while k < discounts, goes to (v, k+1) for d + toll/2 (integer division). We relax whichever improves its stored distance and push it.
The answer is the smallest dist[n-1][k] over all discount counts k, because reaching the destination with leftover discounts is perfectly fine. If every entry stays infinite, the city is unreachable and we return -1.
Worked example: full toll 0→1 costs 4; then spending the one discount on 1→4 turns toll 11 into 5. Total 4 + 5 = 9, which beats any all-full-toll route, so the answer is 9.