LeetCode 2093 - Minimum Cost to Reach City With Discounts

LeetCode Problem 2093

Difficulty: 🟡 Medium
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

This problem describes a weighted, undirected graph where each city is a node and each highway is an edge with an associated toll cost. The goal is to travel from city 0 to city n - 1 while minimizing the total travel cost.

The special twist is the presence of discounts. A discount can be applied to a highway traversal, reducing the toll from toll to toll // 2, using integer division. Each discount can only be used once, and at most one discount may be applied per highway traversal.

The input consists of:

• n, the total number of cities
• highways, where each entry [u, v, toll] represents a bidirectional edge between cities u and v
• discounts, the number of discounts available

The output should be the minimum total cost required to travel from city 0 to city n - 1. If no path exists, the result should be -1.

The constraints are important because they guide the algorithm choice:

• n <= 1000
• highways.length <= 1000
• discounts <= 500

A graph with 1000 nodes and 1000 edges is relatively sparse. However, the discount dimension significantly increases the state space. A naive shortest path algorithm that ignores discounts will not work because the best path depends not only on the current city, but also on how many discounts have already been used.

Several edge cases are important:

• The destination may be unreachable.
• There may be zero discounts available.
• A path with more edges may become cheaper if discounts are used strategically.
• Using a discount early is not always optimal.
• Toll values can be zero.
• Multiple visits to the same city may be necessary if different discount counts produce different costs.

Because the state depends on both position and remaining discount usage, the problem naturally becomes a shortest path problem on an expanded state graph.

Approaches

Brute Force Approach

A brute force solution would attempt to enumerate every possible path from city 0 to city n - 1, while also trying every possible combination of discount usage across the traversed highways.

For each path, we could compute the minimum achievable cost by deciding which edges receive discounts. Since each edge traversal has two possibilities, discounted or not discounted, the number of combinations grows exponentially.

This approach is correct because it eventually examines all valid possibilities. However, it is far too slow. The graph may contain cycles, and the number of paths can become enormous. Even if we restrict ourselves to simple paths, the number of possible routes is exponential in the number of nodes.

The brute force strategy is computationally infeasible for the given constraints.

Key Insight

The key observation is that the optimal state is determined by two pieces of information:

1. The current city
2. The number of discounts already used

Reaching the same city with a different number of discounts remaining can lead to completely different future costs. Therefore, we cannot use a traditional single-distance Dijkstra algorithm.

Instead, we treat (city, discounts_used) as a unique state.

This transforms the problem into a shortest path problem over an expanded graph:

• Original graph nodes become layered states
• Each layer corresponds to how many discounts have been used

From a state (u, d):

• We may travel normally to (v, d) with cost toll
• If d < discounts, we may use a discount and travel to (v, d + 1) with cost toll // 2

All edge weights remain non-negative, which means Dijkstra's algorithm is still applicable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all paths and discount combinations
Optimal	O((n × discounts + highways) log(n × discounts))	O(n × discounts)	Dijkstra on expanded state graph

Algorithm Walkthrough

1. Build an adjacency list for the graph.

Since the highways are bidirectional, each edge [u, v, toll] is added in both directions. The adjacency list allows efficient neighbor traversal. 2. Create a distance table.

Define:

dist[city][used_discounts]

This stores the minimum cost required to reach city after using exactly used_discounts discounts.

Initialize all values to infinity. 3. Initialize the starting state.

We begin at city 0 with cost 0 and no discounts used.

dist[0][0] = 0

4. Use a priority queue for Dijkstra's algorithm.

Each heap entry contains:

(current_cost, city, discounts_used)

The heap always processes the currently cheapest reachable state first. 5. Process states from the heap.

Pop the minimum-cost state.

If this state is already worse than the recorded distance, skip it. This is the standard Dijkstra optimization. 6. Explore neighbors without using a discount.

For every neighboring city:

new_cost = current_cost + toll

If this improves dist[next_city][discounts_used], update it and push the new state into the heap. 7. Explore neighbors using a discount.

If discounts are still available:

discounted_cost = current_cost + toll // 2

This transitions to:

(next_city, discounts_used + 1)

Again, update the distance table if the new path is better. 8. Continue until the heap is empty.

Since Dijkstra guarantees shortest-first processing, the first optimal route to each state is eventually finalized. 9. Compute the answer.

The destination city may be reached using different numbers of discounts.

Therefore, the final answer is:

min(dist[n - 1])

If all values remain infinity, return -1.

Why it works

Dijkstra's algorithm works because all edge weights are non-negative, even after discount application.

The expanded state graph correctly models every valid situation. A state uniquely captures both location and discount usage history. Every legal movement corresponds to an edge in this expanded graph.

Since Dijkstra always processes the currently cheapest unprocessed state, once a state is finalized, its shortest distance is guaranteed to be optimal.

Therefore, the algorithm correctly computes the minimum achievable travel cost.

Python Solution

from typing import List
import heapq

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        graph = [[] for _ in range(n)]

        for u, v, toll in highways:
            graph[u].append((v, toll))
            graph[v].append((u, toll))

        INF = float("inf")

        dist = [[INF] * (discounts + 1) for _ in range(n)]
        dist[0][0] = 0

        min_heap = [(0, 0, 0)]
        # (cost, city, discounts_used)

        while min_heap:
            current_cost, city, used = heapq.heappop(min_heap)

            if current_cost > dist[city][used]:
                continue

            for neighbor, toll in graph[city]:
                # Travel without discount
                normal_cost = current_cost + toll

                if normal_cost < dist[neighbor][used]:
                    dist[neighbor][used] = normal_cost
                    heapq.heappush(
                        min_heap,
                        (normal_cost, neighbor, used)
                    )

                # Travel with discount
                if used < discounts:
                    discounted_cost = current_cost + toll // 2

                    if discounted_cost < dist[neighbor][used + 1]:
                        dist[neighbor][used + 1] = discounted_cost
                        heapq.heappush(
                            min_heap,
                            (discounted_cost, neighbor, used + 1)
                        )

        answer = min(dist[n - 1])

        return answer if answer != INF else -1

The implementation begins by constructing an adjacency list representation of the graph. Since the highways are bidirectional, every edge is inserted twice.

The dist table is the most important structure in the solution. Instead of storing only one best distance per city, it stores one distance for every possible number of discounts used. This is necessary because reaching the same city with different remaining discounts creates different future opportunities.

The priority queue drives Dijkstra's algorithm. Each state includes the accumulated cost, the current city, and how many discounts have already been consumed.

For every neighboring edge, the code explores two transitions:

• Travel normally
• Travel using a discount

If either produces a better state than previously known, the distance table is updated and the state is pushed into the heap.

At the end, the algorithm checks all possible discount usages for the destination city and returns the minimum.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type State struct {
	cost int
	city int
	used int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func minimumCost(n int, highways [][]int, discounts int) int {
	graph := make([][][2]int, n)

	for _, edge := range highways {
		u := edge[0]
		v := edge[1]
		toll := edge[2]

		graph[u] = append(graph[u], [2]int{v, toll})
		graph[v] = append(graph[v], [2]int{u, toll})
	}

	inf := math.MaxInt

	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, discounts+1)

		for j := 0; j <= discounts; j++ {
			dist[i][j] = inf
		}
	}

	dist[0][0] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{
		cost: 0,
		city: 0,
		used: 0,
	})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		currentCost := current.cost
		city := current.city
		used := current.used

		if currentCost > dist[city][used] {
			continue
		}

		for _, edge := range graph[city] {
			neighbor := edge[0]
			toll := edge[1]

			// Without discount
			normalCost := currentCost + toll

			if normalCost < dist[neighbor][used] {
				dist[neighbor][used] = normalCost

				heap.Push(pq, State{
					cost: normalCost,
					city: neighbor,
					used: used,
				})
			}

			// With discount
			if used < discounts {
				discountedCost := currentCost + toll/2

				if discountedCost < dist[neighbor][used+1] {
					dist[neighbor][used+1] = discountedCost

					heap.Push(pq, State{
						cost: discountedCost,
						city: neighbor,
						used: used + 1,
					})
				}
			}
		}
	}

	answer := inf

	for d := 0; d <= discounts; d++ {
		if dist[n-1][d] < answer {
			answer = dist[n-1][d]
		}
	}

	if answer == inf {
		return -1
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version, but requires a manual priority queue implementation using the container/heap package.

The adjacency list stores pairs as fixed-size arrays [2]int, where the first element is the neighbor and the second is the toll.

Go does not provide infinity values for integers directly, so math.MaxInt is used as the initial unreachable distance.

Because Go's heap interface works with interface{}, explicit type assertions are required during push and pop operations.

Worked Examples

Example 1

n = 5
highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]]
discounts = 1

Initial State

Heap	Meaning
(0, 0, 0)	cost = 0, city = 0, discounts used = 0

Step 1

Pop (0, 0, 0).

Neighbors:

Move	Cost	New State
0 → 1 normally	4	(4, 1, 0)
0 → 1 discounted	2	(2, 1, 1)

Heap becomes:

Heap Contents
(2,1,1)
(4,1,0)

Step 2

Pop (2,1,1).

No discounts remain.

Neighbors:

Move	Cost	State
1 → 2	5	(5,2,1)
1 → 4	13	(13,4,1)

Step 3

Pop (4,1,0).

Neighbors:

Move	Cost	State
1 → 4 normally	15	(15,4,0)
1 → 4 discounted	9	(9,4,1)

Now the destination is reachable with cost 9.

No future state can improve this result, so the final answer is:

9

Example 2

n = 4
highways = [[1,3,17],[1,2,7],[3,2,5],[0,1,6],[3,0,20]]
discounts = 20

The algorithm explores many states, but the optimal route becomes:

Edge	Discount Applied	Cost
0 → 1	Yes	3
1 → 2	Yes	3
2 → 3	Yes	2

Total:

3 + 3 + 2 = 8

Example 3

n = 4
highways = [[0,1,3],[2,3,2]]
discounts = 0

The graph is disconnected.

The algorithm never reaches city 3, so all entries in:

dist[3][*]

remain infinity.

Therefore:

return -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n × discounts + highways × discounts) log(n × discounts))	Each state may enter the heap and process edges
Space	O(n × discounts)	Distance table and heap storage

The graph is expanded into multiple layers based on discount usage. Each city can appear in up to discounts + 1 states.

For every state, we may traverse all adjacent edges. Since Dijkstra's algorithm uses a priority queue, every insertion and removal costs logarithmic time relative to the number of states.

The distance table dominates the memory usage.

Test Cases

from typing import List

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        import heapq

        graph = [[] for _ in range(n)]

        for u, v, toll in highways:
            graph[u].append((v, toll))
            graph[v].append((u, toll))

        INF = float("inf")

        dist = [[INF] * (discounts + 1) for _ in range(n)]
        dist[0][0] = 0

        heap = [(0, 0, 0)]

        while heap:
            cost, city, used = heapq.heappop(heap)

            if cost > dist[city][used]:
                continue

            for nxt, toll in graph[city]:
                # No discount
                if cost + toll < dist[nxt][used]:
                    dist[nxt][used] = cost + toll
                    heapq.heappush(heap, (cost + toll, nxt, used))

                # Use discount
                if used < discounts:
                    discounted = cost + toll // 2

                    if discounted < dist[nxt][used + 1]:
                        dist[nxt][used + 1] = discounted
                        heapq.heappush(
                            heap,
                            (discounted, nxt, used + 1)
                        )

        ans = min(dist[n - 1])

        return ans if ans != INF else -1

sol = Solution()

assert sol.minimumCost(
    5,
    [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]],
    1
) == 9  # Provided example 1

assert sol.minimumCost(
    4,
    [[1,3,17],[1,2,7],[3,2,5],[0,1,6],[3,0,20]],
    20
) == 8  # Provided example 2

assert sol.minimumCost(
    4,
    [[0,1,3],[2,3,2]],
    0
) == -1  # Disconnected graph

assert sol.minimumCost(
    2,
    [[0,1,10]],
    0
) == 10  # Single edge without discount

assert sol.minimumCost(
    2,
    [[0,1,10]],
    1
) == 5  # Single edge with discount

assert sol.minimumCost(
    3,
    [[0,1,1],[1,2,1],[0,2,100]],
    1
) == 1  # Discount applied to expensive direct edge

assert sol.minimumCost(
    3,
    [[0,1,5],[1,2,5]],
    10
) == 4  # More discounts than needed

assert sol.minimumCost(
    3,
    [[0,1,0],[1,2,0]],
    1
) == 0  # Zero toll highways

assert sol.minimumCost(
    1,
    [],
    0
) == 0  # Start already equals destination

assert sol.minimumCost(
    4,
    [[0,1,100],[1,3,1],[0,2,1],[2,3,100]],
    1
) == 51  # Optimal discount placement matters

Test Summary

Test	Why
Example 1	Standard mixed graph case
Example 2	Many discounts available
Example 3	Destination unreachable
Single edge without discount	Basic shortest path
Single edge with discount	Basic discount usage
Expensive shortcut	Strategic discount placement
Excess discounts	Handles large discount counts
Zero toll edges	Verifies zero-weight behavior
Single node graph	Start equals destination
Competing discount choices	Ensures optimal state tracking

Edge Cases

One important edge case is when the graph is disconnected. A naive implementation might assume that every city is reachable, but this is not guaranteed. In such situations, the destination state's distances remain infinity. The implementation correctly detects this and returns -1.

Another important edge case occurs when there are more discounts available than useful edges in the optimal path. The algorithm does not force all discounts to be used. Instead, it tracks all possible discount counts independently and selects the minimum among them at the destination.

A subtle edge case involves revisiting the same city multiple times with different discount counts. A traditional shortest path implementation that stores only one distance per city would fail here. For example, reaching a city cheaply after consuming all discounts may actually be worse than reaching it slightly more expensively while preserving discounts for later. The expanded state representation handles this correctly.

A final edge case involves tolls equal to zero. Since integer division of zero is still zero, discount application changes nothing. The implementation naturally handles this because Dijkstra's algorithm supports non-negative edge weights, including zero.