LeetCode Solutions Blog

Minimum Cost to Reach City With Discounts

Number: 2230

Difficulty: Medium

Paid? Yes

Companies: Flipkart

Problem Description

Given n cities connected by highways, each with a specified toll, you need to find the minimum cost to travel from city 0 to city n - 1. You also have a number of discounts available, where a discount lets you traverse a highway at half its toll cost (using integer division). Each highway can use at most one discount and each discount can only be used once. If it is not possible to reach city n - 1, return -1.

Key Insights

This is a shortest path problem on an undirected weighted graph.
The twist is the limited number of discounts that can be applied, which leads to an augmented state-space.
Each state can be represented by (city, discountsUsed), and we need to track the cost accordingly.
A modified Dijkstra's algorithm can be applied by taking into consideration whether to use a discount on a given edge.
The challenge is to consider both scenarios: using a discount (if available) and not using one when transitioning between cities.

Space and Time Complexity

Time Complexity: O(highways.length * (discounts + 1) * log(n * (discounts + 1))) Space Complexity: O(n * (discounts + 1)) for the distance/state tracking structure.

Solution

We solve the problem using a modified Dijkstra's algorithm, which tracks an augmented state defined by the current city and the number of discounts used so far. A min-heap (priority queue) is used, where each element is (currentCost, currentCity, usedDiscounts). For every neighboring city of the current state, we explore two possibilities:

Traverse the edge without applying a discount.
Traverse the edge with a discount (provided we still have discounts remaining). The distance table is updated for every state, and the process continues until either the destination is reached or all states are processed.

Code Solutions

import heapq

def minimumCost(n, highways, discounts):
    # Build the graph as an adjacency list
    graph = [[] for _ in range(n)]
    for u, v, toll in highways:
        graph[u].append((v, toll))
        graph[v].append((u, toll))
    
    # Initialize a 2D array for distances: dist[city][discounts_used]
    max_discounts = discounts + 1
    dist = [[float('inf')] * max_discounts for _ in range(n)]
    dist[0][0] = 0
    
    # Priority queue: (current_cost, current_city, used_discounts)
    heap = [(0, 0, 0)]
    
    while heap:
        current_cost, city, used_discount = heapq.heappop(heap)
        
        # If we reached the destination, check for best answer
        if city == n - 1:
            return current_cost
        
        # Skip state if we already have a better cost recorded
        if current_cost > dist[city][used_discount]:
            continue
        
        # Explore neighbors
        for neighbor, toll in graph[city]:
            # Option 1: Travel without using a discount
            new_cost = current_cost + toll
            if new_cost < dist[neighbor][used_discount]:
                dist[neighbor][used_discount] = new_cost
                heapq.heappush(heap, (new_cost, neighbor, used_discount))
            
            # Option 2: Use a discount if available (only one per highway)
            if used_discount < discounts:
                # Calculate discounted cost (using integer division)
                discounted_cost = current_cost + (toll // 2)
                if discounted_cost < dist[neighbor][used_discount + 1]:
                    dist[neighbor][used_discount + 1] = discounted_cost
                    heapq.heappush(heap, (discounted_cost, neighbor, used_discount + 1))
    
    # If unreachable, return -1
    return -1

# Example test cases
print(minimumCost(5, [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], 1))  # Output: 9
print(minimumCost(4, [[1,3,17],[1,2,7],[3,2,5],[0,1,6],[3,0,20]], 20))  # Output: 8