Problem Description

You have n cities numbered from 0 to n - 1 connected by highways. Each highway is bidirectional and has a toll cost. You're given:

• highways[i] = [city1, city2, toll]: a highway connecting city1 and city2 with cost toll
• discounts: the number of discount coupons you have

You need to find the minimum cost to travel from city 0 to city n - 1.

Key rules for using discounts:

• Each discount reduces a highway's toll to toll / 2 (integer division)
• You can use at most one discount per highway
• Each discount can only be used once
• You have a total of discounts number of discounts available

The problem asks you to return:

• The minimum total cost to reach city n - 1 from city 0
• Return -1 if it's impossible to reach city n - 1 from city 0

Example breakdown:

• In Example 1, with 1 discount available, the optimal path is 0 → 1 (cost 4) then 1 → 4 with discount (cost 11/2 = 5), totaling 9.
• In Example 2, with 20 discounts (more than needed), you can use discounts on every highway in the path 0 → 1 → 2 → 3, getting costs of 3 + 3 + 2 = 8.
• In Example 3, there's no path connecting city 0 to city 3, so the answer is -1.

This is essentially a shortest path problem with the added complexity of managing a limited number of discounts that can reduce edge weights by half.

Intuition

This problem is a variation of the classic shortest path problem, but with an extra dimension - we can modify edge weights by using discounts. The key insight is that we need to track not just "what's the shortest path to each city" but rather "what's the shortest path to each city using exactly k discounts."

Think of it this way: when we're at a city, we have multiple states based on how many discounts we've used so far. For example, reaching city 2 with 0 discounts used might cost 10, but reaching city 2 with 1 discount used might cost 7. These are different states that could lead to different optimal paths to the destination.

This naturally leads us to think about Dijkstra's algorithm, but instead of maintaining a single distance value for each node, we maintain a 2D array dist[city][discounts_used] that tracks the minimum cost to reach each city with a specific number of discounts used.

When we explore from a current city, we have two choices for each neighboring highway:

1. Take the highway at full price (don't use a discount)
2. Take the highway at half price (use a discount if we have any left)

Both choices create new states: (next_city, same_discount_count) and (next_city, discount_count + 1). We explore all these states using a priority queue, always processing the lowest cost state first.

The algorithm terminates when we reach city n-1 for the first time (since we're using Dijkstra's with a min-heap, the first time we reach the destination is guaranteed to be the minimum cost), or when we've exhausted all reachable states without reaching the destination (returning -1).

The beauty of this approach is that it automatically finds the optimal balance between using discounts on expensive highways versus saving them for later, because it explores all possible combinations in order of increasing cost.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements a modified Dijkstra's algorithm with state tracking for discount usage. Let's walk through the implementation step by step:

1. Build the Graph:

g = defaultdict(list)
for a, b, c in highways:
    g[a].append((b, c))
    g[b].append((a, c))

We create an adjacency list representation of the graph. Since highways are bidirectional, we add edges in both directions.

2. Initialize Data Structures:

q = [(0, 0, 0)]  # (cost, city, discounts_used)
dist = [[inf] * (discounts + 1) for _ in range(n)]

• q: A min-heap (priority queue) initialized with the starting state: cost=0, city=0, discounts_used=0
• dist[i][k]: A 2D array where dist[i][k] represents the minimum cost to reach city i using exactly k discounts

3. Process States with Dijkstra's Algorithm:

while q:
    cost, i, k = heappop(q)
    if k > discounts:
        continue
    if i == n - 1:
        return cost

We continuously extract the state with minimum cost. If we've used too many discounts, skip this state. If we've reached the destination city n-1, return the cost immediately (first arrival guarantees minimum cost due to the priority queue).

4. Update Distances and Explore Neighbors:

if dist[i][k] > cost:
    dist[i][k] = cost
    for j, v in g[i]:
        heappush(q, (cost + v, j, k))      # Don't use discount
        heappush(q, (cost + v // 2, j, k + 1))  # Use discount

Only process this state if it offers a better cost than previously recorded. For each neighbor j with toll v:

• Add state without using discount: (cost + v, j, k)
• Add state with discount: (cost + v // 2, j, k + 1) where v // 2 is integer division

5. Handle Unreachable Case:

return -1

If the queue is exhausted without reaching city n-1, the destination is unreachable.

Time Complexity: O((V * D + E * D) * log(V * D)) where V is the number of cities, E is the number of highways, and D is the number of discounts. Each state (city, discounts_used) can be pushed to the heap multiple times, and heap operations take logarithmic time.

Space Complexity: O(V * D) for the distance array plus the heap size which can grow up to O(E * D) in the worst case.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example:

• Cities: 0, 1, 2, 3 (n = 4)
• Highways: [[0,1,5], [1,2,7], [0,2,10], [2,3,3]]
• Discounts: 1
• Goal: Find minimum cost from city 0 to city 3

Step-by-step execution:

Initial Setup:

• Graph adjacency list:
  • 0: [(1,5), (2,10)]
  • 1: [(0,5), (2,7)]
  • 2: [(1,7), (0,10), (3,3)]
  • 3: [(2,3)]
• Priority queue: [(0, 0, 0)] (cost=0, city=0, discounts_used=0)
• Distance array: All initialized to infinity

Iteration 1: Pop (0, 0, 0)

• Current state: cost=0, city=0, discounts_used=0
• Update dist[0][0] = 0
• Add neighbors:
  • To city 1: (5, 1, 0) without discount, (2, 1, 1) with discount
  • To city 2: (10, 2, 0) without discount, (5, 2, 1) with discount
• Queue: [(2,1,1), (5,1,0), (5,2,1), (10,2,0)]

Iteration 2: Pop (2, 1, 1)

• Current state: cost=2, city=1, discounts_used=1
• Update dist[1][1] = 2
• Add neighbors:
  • To city 0: (7, 0, 1) without discount (skip discount, already used 1)
  • To city 2: (9, 2, 1) without discount (skip discount option)
• Queue: [(5,1,0), (5,2,1), (7,0,1), (9,2,1), (10,2,0)]

Iteration 3: Pop (5, 1, 0)

• Current state: cost=5, city=1, discounts_used=0
• Update dist[1][0] = 5
• Add neighbors:
  • To city 0: (10, 0, 0) without discount, (7, 0, 1) with discount
  • To city 2: (12, 2, 0) without discount, (8, 2, 1) with discount
• Queue: [(5,2,1), (7,0,1), (8,2,1), (9,2,1), (10,0,0), (10,2,0), (12,2,0)]

Iteration 4: Pop (5, 2, 1)

• Current state: cost=5, city=2, discounts_used=1
• Update dist[2][1] = 5
• Add neighbors:
  • To city 1: (12, 1, 1) without discount
  • To city 0: (15, 0, 1) without discount
  • To city 3: (8, 3, 1) without discount (can't use more discounts)
• Queue: [(7,0,1), (8,2,1), (8,3,1), (9,2,1), (10,0,0), (10,2,0), (12,1,1), (12,2,0), (15,0,1)]

Iteration 5: Pop (7, 0, 1)

• Already visited dist[0][1] = 7 (not better than infinity, so process)
• Skip for brevity...

Iteration 6: Pop (8, 2, 1)

• Cost 8 > dist[2][1] = 5, skip

Iteration 7: Pop (8, 3, 1)

• Reached destination city 3!
• Return cost = 8

Final Answer: The minimum cost is 8

• Optimal path: 0 → 1 (using discount: 5/2=2) → 2 (no discount: 7) → 3 (no discount: 3)
• Total: 2 + 7 + 3 = 12 (wait, let's recalculate...)

Actually, let me trace the optimal path more carefully:

• 0 → 2 (using discount: 10/2=5) → 3 (no discount: 3)
• Total: 5 + 3 = 8 ✓

The algorithm correctly finds that using our single discount on the expensive 0→2 highway (reducing it from 10 to 5) and then taking the 2→3 highway at full price gives us the minimum total cost of 8.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * k * m * log(n * k * m)) where n is the number of nodes, k is the number of discounts, and m is the number of edges (highways).

• The algorithm uses Dijkstra's algorithm with a modified state space that includes both the current node and the number of discounts used.
• Each state (node, discounts_used) can be visited, creating up to n * (k + 1) possible states.
• For each state, we explore all adjacent edges. In the worst case, a node can have up to m edges.
• Each edge exploration results in two heap push operations (one with discount, one without).
• This gives us up to 2 * m * n * (k + 1) heap operations.
• Each heap operation (push/pop) takes O(log(heap_size)) time, where the heap can grow up to O(n * k * m) in size.
• Therefore, the overall time complexity is O(n * k * m * log(n * k * m)).

Space Complexity: O(n * k + m + n * k * m)

• The dist array uses O(n * (k + 1)) = O(n * k) space to store the minimum cost for each (node, discounts_used) combination.
• The adjacency list g stores all edges, using O(m) space where each edge is stored twice (undirected graph).
• The priority queue q can contain up to O(n * k * m) elements in the worst case, as each state can generate multiple entries before being processed.
• Therefore, the total space complexity is O(n * k + m + n * k * m) which simplifies to O(n * k * m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Discount Limit Properly

A common mistake is allowing states where discounts_used exceeds the available discounts. While the current code checks this condition (if discounts_used > discounts: continue), a more efficient approach would be to prevent these invalid states from being added to the queue in the first place.

Problem: The current implementation adds states with discounts_used + 1 even when discounts_used might already equal discounts, creating unnecessary states in the queue.

Solution:

# Explore all neighboring cities
for next_city, toll_cost in graph[current_city]:
    # Option 1: Travel without using a discount
    heappush(priority_queue, (current_cost + toll_cost, next_city, discounts_used))
  
    # Option 2: Travel using a discount (only if we have discounts left)
    if discounts_used < discounts:  # Add this check
        heappush(priority_queue, (current_cost + toll_cost // 2, next_city, discounts_used + 1))

2. Revisiting Already Processed States

The current implementation checks if a state offers a better cost before processing its neighbors, but it doesn't prevent revisiting already optimally processed states. This can lead to redundant computations.

Problem: A state (city, discounts_used) might be processed multiple times if it appears in the queue with different costs.

Solution: Add a visited set to track processed states:

visited = set()

while priority_queue:
    current_cost, current_city, discounts_used = heappop(priority_queue)
  
    # Skip if already processed this state optimally
    if (current_city, discounts_used) in visited:
        continue
    visited.add((current_city, discounts_used))
  
    # Rest of the logic...

3. Integer Division Edge Case

When using a discount, the toll becomes toll // 2. For odd tolls, this rounds down (e.g., 5 // 2 = 2), which is correct per the problem specification. However, some might mistakenly use regular division or forget about the rounding behavior.

Problem: Using toll / 2 instead of toll // 2 would result in float values and incorrect calculations.

Solution: Always use integer division (//) when applying discounts, as shown in the correct implementation.

4. Initializing Distance Array Incorrectly

The distance array needs to track the minimum cost for each combination of (city, discounts_used). A common mistake is creating a 1D array or incorrectly sized 2D array.

Problem: Using dist = [float('inf')] * n or dist = [[float('inf')] * discounts for _ in range(n)] (missing the +1).

Solution: The array should be (discounts + 1) in the second dimension to account for states from 0 to discounts discounts used:

distance = [[float('inf')] * (discounts + 1) for _ in range(n)]