2093. Minimum Cost to Reach City With Discounts

MediumGraphShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

This problem deals with finding the minimum total cost of traversing from one city to another across a network of highways that connect various cities. Each highway has an associated toll cost, and you have a given number of discounts that can be used to halve the toll on any highway, although each discount can only be applied once and to only one highway at a time.

You are given:

  1. An integer n, which is the total number of cities labeled from 0 to n - 1.
  2. A 2D array highways, where each highways[i] contains three integers representing two cities connected by a highway (city1i and city2i) and the toll cost (toll_i) for traversing that highway.
  3. An integer discounts representing the number of discounts available.

The goal is to compute the minimum total cost required to travel from city 0 to city n - 1. If it's not possible to complete the journey, the function should return -1.

Intuition

The intuition behind the solution is to use a modified Dijkstra's algorithm to find the shortest path from the starting city to the destination city. Dijkstra's algorithm is a greedy approach that selects the minimum-weight edge at each step to find the shortest path between two vertices in a graph with non-negative edge weights.

Since we have to account for the possible discounts, we can treat each state in our priority queue as a tuple containing the current cost, the current city, and the number of discounts used so far. This way, we expand our search from each city to its adjacent cities with the consideration of whether or not to use a discount.

Modifications to the standard Dijkstra's algorithm include:

  • Tracking the number of discounts used for reaching each city to accurately choose when to apply a discount.
  • Adding two possible states for each adjacent city to the priority queue: one with an additional discount used and one without an additional discount, with the corresponding cost of the highway travel.
  • When a city is reached, if there are still remaining discounts, we can consider further paths from this city using the remaining discounts, hence maintaining dist as a 2D array where dist[i][k] represents the minimum cost to reach city i with k discounts used.
  • The priority queue keeps track of the cost, ensuring the shortest path with the available discounts is prioritized.

Only if the destination city is reached and the cost is less than the previous known costs to reach that city with the same or a lesser number of discounts used, we can conclude that the path is indeed the minimum cost path that utilizes the available discounts effectively. If we can reach the destination (n - 1), we return the cost. If the destination can't be reached, we return -1.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which type of traversal does breadth first search do?

Solution Approach

The solution implements a modified version of Dijkstra's algorithm, which is best suited for finding the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.

Here's a breakdown of the implementation steps:

  1. Initialize a graph g as a defaultdict(list) to store the adjacency list representation of highways, with each list item being a tuple containing the destination city and toll cost.

  2. Prepare a priority queue q and seed it with an initial state (0, 0, 0), indicating a starting cost of 0, from city 0, with 0 discounts used.

  3. Initialize a 2D list dist of size n x (discounts + 1) with inf to store the minimum cost to reach each city using a certain number of discounts. This accounts for the different states of each city according to the discounts used.

  4. While the priority queue q is not empty, pop the minimum cost state, which consists of (cost, current ith city, and number of discounts k used so far).

  5. If we've reached the destination city (i == n - 1), we return the current cost as the minimum cost found.

  6. If visiting this city and discount state is cheaper than a previously visited state (dist[i][k] > cost), update dist[i][k] with the new cost.

  7. For each neighboring city (j) from the current city along with its highway toll (v), push two new states onto the priority queue:

    • One without using a discount: (cost + v, j, k)
    • One with using a discount (if available, i.e., k < discounts): (cost + v // 2, j, k + 1)

The use of a heap-based priority queue ensures that the state with the minimum cost is always processed first (heap property), which is critical for the greedy approach.

The algorithm ensures that all cities and discount states are considered, and by keeping the costs updated only when a cheaper path is found, it guarantees finding the minimum cost path considering available discounts.

If no path to the destination city is found, the function returns -1.

The final piece of this implementation uses the heappush method to add states to the queue and heappop to retrieve the lowest-cost state from the queue, maintaining the priority queue's properties.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

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

Suppose we have the following input:

  • The number of cities n = 4, meaning we have cities labeled 0 to 3.
  • The highways array is highways = [[0, 1, 10], [1, 2, 5], [2, 3, 10], [0, 3, 30]], meaning there is a highway from city 0 to city 1 with a toll of 10, from city 1 to city 2 with a toll of 5, from city 2 to city 3 with a toll of 10, and from city 0 to city 3 with a toll of 30.
  • We have discounts = 1, allowing us to use one discount to halve the toll on any one highway.

Here are the solution steps using the example:

  1. Initialize the graph g to represent our cities and highways:

    • Graph g: {0: [(1, 10), (3, 30)], 1: [(2, 5)], 2: [(3, 10)], 3: []}

  2. Begin with the priority queue q containing the initial state (0, 0, 0), representing a cost of 0, starting from city 0, with 0 discounts used.

  3. Prepare the dist table with dimensions 4x2 (since we have 4 cities and discounts + 1 possible discount usages):

    1dist = [
2  [inf, inf],
3  [inf, inf],
4  [inf, inf],
5  [inf, inf]
6]

  4. Process the states in the priority queue q:

    • Pop the state (0, 0, 0) from q. It's the starting city with a cost of 0, and no discounts have been used.
    • Update dist[0][0] with 0.

  5. From city 0, consider the neighbors:

    • City 1, with a toll of 10. We can either:
      • Pay the full toll: push (10, 1, 0) into q.
      • Use the discount: push (5, 1, 1) into q.
    • City 3, with a toll of 30. We can either:
      • Pay the full toll: push (30, 3, 0) into q.
      • Use the discount: push (15, 3, 1) into q.

  6. Continue processing the states:

    • The state (5, 1, 1) is now the cheapest in q.
    • Update dist[1][1] with 5.
    • From city 1, consider the neighbor city 2, with a toll of 5. We can't use any more discounts, but we push (10, 2, 1) into q.

  7. Eventually, we will process the state (10, 2, 1):

    • Update dist[2][1] with 10.
    • From city 2, consider the neighbor city 3, with a toll of 10. We push (20, 3, 1) into q.

  8. The state (20, 3, 1) is processed:

    • Since 3 is the destination city and we cannot get a lower cost with 1 discount used, update dist[3][1] with 20.

  9. Since we have reached the destination city 3, and no other path provides a cheaper route, the minimum cost returned is 20.

In summary, the path taken for the minimum cost is 0 -> 1 with a discount applied, 1 -> 2 at full toll, and 2 -> 3 also at full toll, resulting in a total cost of 5 (half the toll for highway 0-1) + 5 (toll for highway 1-2) + 10 (toll for highway 2-3) = 20.

If we had no path to city 3, our function would return -1, but in this case, we have successfully found the minimum cost path with the use of discounts, which is 20.

Solution Implementation

1from heapq import heappush, heappop
2from collections import defaultdict
3from typing import List
4
5class Solution:
6    def minimum_cost(self, cities: int, highways: List[List[int]], discounts: int) -> int:
7        # Create a graph to store city connections and costs
8        graph = defaultdict(list)
9        for city_from, city_to, cost in highways:
10            graph[city_from].append((city_to, cost))
11            graph[city_to].append((city_from, cost))
12      
13        # Initialize a priority queue with starting point information
14        # (cost to reach city, current city, current number of discounts used)
15        queue = [(0, 0, 0)]
16      
17        # Initialize distance table to keep track of the minimum cost with varying number of discounts applied
18        distance = [[float('inf')] * (discounts + 1) for _ in range(cities)]
19      
20        # Continue until the queue is empty
21        while queue:
22            # Dequeue the next (cost, current city, discounts used)
23            current_cost, current_city, used_discounts = heappop(queue)
24          
25            # Ignore paths where we've exceeded the number of discounts available
26            if used_discounts > discounts:
27                continue
28          
29            # Check if we've reached the destination with this path
30            if current_city == cities - 1:
31                return current_cost
32          
33            # If this is the best cost for this city with this number of used discounts, update it
34            if distance[current_city][used_discounts] > current_cost:
35                distance[current_city][used_discounts] = current_cost
36              
37                # Explore paths from the current city
38                for next_city, next_cost in graph[current_city]:
39                    # Add path to the same city with no discount used
40                    heappush(queue, (current_cost + next_cost, next_city, used_discounts))
41                    # Add path to the same city with a discount, if we have any left
42                    if used_discounts < discounts:
43                        heappush(queue, (current_cost + next_cost // 2, next_city, used_discounts + 1))
44      
45        # If the destination city was not reached return -1
46        return -1
47
1class Solution {
2  
3    // Function to calculate the minimum cost to travel from node 0 to node n-1.
4    public int minimumCost(int n, int[][] highways, int discounts) {
5        // Create an adjacency list for the graph
6        List<int[]>[] graph = new List[n];
7        for (int i = 0; i < n; ++i) {
8            graph[i] = new ArrayList<>();
9        }
10      
11        // Populate the adjacency list with the given highways information
12        for (int[] highway : highways) {
13            int from = highway[0], to = highway[1], cost = highway[2];
14            graph[from].add(new int[] {to, cost});
15            graph[to].add(new int[] {from, cost});
16        }
17      
18        // Priority queue to hold the nodes for processing based on cost (min-heap)
19        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
20        // Seed queue with the starting node (cost, index, discounts used)
21        queue.offer(new int[] {0, 0, 0});
22      
23        // Distance array to keep track of the minimum cost with discounts used at each node
24        int[][] dist = new int[n][discounts + 1];
25        for (int[] distances : dist) {
26            Arrays.fill(distances, Integer.MAX_VALUE);
27        }
28      
29        // Dijkstra's algorithm with the ability to use discounts
30        while (!queue.isEmpty()) {
31            int[] poll = queue.poll();
32            int cost = poll[0];
33            int nodeIndex = poll[1];
34            int usedDiscounts = poll[2];
35          
36            // Skip if we've found a better way already or exceeded discount limits
37            if (usedDiscounts > discounts || dist[nodeIndex][usedDiscounts] <= cost) {
38                continue;
39            }
40          
41            // Return the cost if we have reached the destination
42            if (nodeIndex == n - 1) {
43                return cost;
44            }
45          
46            // Update the distance array
47            dist[nodeIndex][usedDiscounts] = cost;
48          
49            // Explore all adjacent nodes
50            for (int[] next : graph[nodeIndex]) {
51                int neighbor = next[0], neighborCost = next[1];
52                // Offer the regular cost to visit the neighbor
53                queue.offer(new int[] {cost + neighborCost, neighbor, usedDiscounts});
54                // If applicable, offer the discounted cost to visit the neighbor
55                if (usedDiscounts < discounts) {
56                    queue.offer(new int[] {cost + neighborCost / 2, neighbor, usedDiscounts + 1});
57                }
58            }
59        }
60      
61        // Return -1 if there is no path from node 0 to node n-1
62        return -1;
63    }
64}
65
1class Solution {
2public:
3    // Calculates the minimum cost to travel from node 0 to node n-1 given the number 
4    // of available discounts and a list of highways represented as edges with costs.
5    int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
6        // Create a graph with each node having a list of pairs (neighbor, cost).
7        vector<vector<pair<int, int>>> graph(n);
8        for (auto& highway : highways) {
9            int from = highway[0], to = highway[1], cost = highway[2];
10            graph[from].push_back({to, cost});
11            graph[to].push_back({from, cost});
12        }
13      
14        // Use a min-heap to store the state as a tuple of (cost so far, current node, discounts used).
15        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
16        minHeap.push({0, 0, 0});
17
18        // `distanceMatrix` keeps track of the minimum costs with varying numbers of discounts used.
19        vector<vector<int>> distanceMatrix(n, vector<int>(discounts + 1, INT_MAX));
20      
21        // While there are states in the min-heap to process...
22        while (!minHeap.empty()) {
23            // Extract the current state.
24            auto [currentCost, currentNode, usedDiscounts] = minHeap.top();
25            minHeap.pop();
26          
27            // Skip this state if we've used too many discounts or found a better way before.
28            if (usedDiscounts > discounts || distanceMatrix[currentNode][usedDiscounts] <= currentCost) continue;
29          
30            // We've reached the destination with the least cost so far.
31            if (currentNode == n - 1) return currentCost;
32          
33            // Update the distance matrix with the cost for the current node and used discounts.
34            distanceMatrix[currentNode][usedDiscounts] = currentCost;
35          
36            // Explore the neighbors.
37            for (auto [nextNode, nextCost] : graph[currentNode]) {
38                // Go to the next node without using a discount.
39                minHeap.push({currentCost + nextCost, nextNode, usedDiscounts});
40              
41                // Go to the next node using a discount if we have any left.
42                if (usedDiscounts < discounts) {
43                    minHeap.push({currentCost + nextCost / 2, nextNode, usedDiscounts + 1});
44                }
45            }
46        }
47      
48        // Return -1 if the destination node is unreachable.
49        return -1;
50    }
51};
52
1type Highway = [number, number, number]; // Representing a highway as a tuple of [from, to, cost]
2type State = [number, number, number]; // Representing the state as a tuple of [currentCost, currentNode, discountsUsed]
3
4// Comparator for the priority queue
5function stateComparator(a: State, b: State): number {
6    return a[0] - b[0]; // Sort by current cost
7}
8
9// Priority queue class
10class MinHeap<T> {
11    private heap: T[];
12    private comparator: (a: T, b: T) => number;
13
14    constructor(comparator: (a: T, b: T) => number) {
15        this.heap = [];
16        this.comparator = comparator;
17    }
18
19    public isEmpty(): boolean {
20        return this.heap.length === 0;
21    }
22
23    public push(item: T): void {
24        this.heap.push(item);
25        this.heap.sort(this.comparator);
26    }
27
28    public pop(): T | undefined {
29        return this.heap.shift();
30    }
31}
32
33// Calculates the minimum cost to travel from node 0 to node n-1 given the number
34// of available discounts and a list of highways represented as edges with costs.
35function minimumCost(n: number, highways: Highway[], discounts: number): number {
36    // Create a graph with each node having a list of edges (neighbor, cost).
37    const graph: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
38    highways.forEach(([from, to, cost]) => {
39        graph[from].push([to, cost]);
40        graph[to].push([from, cost]);
41    });
42
43    // Use a min-heap to store the state (cost so far, current node, discounts used).
44    const minHeap = new MinHeap<State>(stateComparator);
45    minHeap.push([0, 0, 0]);
46
47    // distanceMatrix keeps track of the minimum costs with varying numbers of discounts used.
48    const distanceMatrix = Array.from({ length: n }, () => Array(discounts + 1).fill(Number.MAX_VALUE));
49
50    // While there are states in the min-heap to process...
51    while (!minHeap.isEmpty()) {
52        // Extract the current state.
53        const currentState = minHeap.pop();
54        if (!currentState) break;
55        const [currentCost, currentNode, usedDiscounts] = currentState;
56
57        // Skip this state if we've used too many discounts or found a better way before.
58        if (usedDiscounts > discounts || distanceMatrix[currentNode][usedDiscounts] <= currentCost) continue;
59
60        // We've reached the destination with the least cost so far.
61        if (currentNode === n - 1) return currentCost;
62
63        // Update the distance matrix with the cost for the current node and used discounts.
64        distanceMatrix[currentNode][usedDiscounts] = currentCost;
65
66        // Explore the neighbors.
67        graph[currentNode].forEach(([nextNode, nextCost]) => {
68            // Go to the next node without using a discount.
69            minHeap.push([currentCost + nextCost, nextNode, usedDiscounts]);
70
71            // Go to the next node using a discount if we have any left.
72            if (usedDiscounts < discounts) {
73                minHeap.push([currentCost + Math.floor(nextCost / 2), nextNode, usedDiscounts + 1]);
74            }
75        });
76    }
77
78    // Return -1 if the destination node is unreachable.
79    return -1;
80}
81
Not Sure What to Study? Take the 2-min Quiz๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The given code represents a solution to the problem of finding the minimum cost from city 0 to city n-1 with the possibility to apply up to discounts discounts on the trip.

Time Complexity

The time complexity of the algorithm can be considered based on the following factors:

  1. Dijkstra's Algorithm: The code resembles an implementation of Dijkstra's algorithm, which usually has a time complexity of O(E + V log V) where E is the number of edges and V is the number of vertices (cities in this case). However, with the use of discounts, it's modified.

  2. Discounts: Since the discounts can be applied discounts times, every edge can potentially be added to the priority queue at most discounts + 1 times (one time without discount and discounts times with each discount level).

  3. Priority Queue Operations: The heappush and heappop operations take O(log N) time where N is the number of elements in the priority queue. Since every edge can be added discounts + 1 times, the number of elements will roughly be O((discounts + 1) * E).

Combining these considerations, the time complexity is roughly O((discounts + 1) * E * log((discounts + 1) * E)) because the number of elements in the priority queue is multiplied by the factor reflecting the application of discounts.

Space Complexity

The space complexity can be analyzed as:

  1. Graph Representation: The graph is stored in a dictionary where each city may have at most E/2 connections (in a fully connected scenario), resulting in O(E) space.

  2. Distance Array: The dist array has a size of n x (discounts + 1) to track the shortest distance to each city given a specific number of discounts used, giving us O(n * (discounts + 1)) space.

  3. Priority Queue: The maximum size of the priority queue can be O((discounts + 1) * E) due to the reasons given in time complexity analysis.

Hence, the space complexity is the sum of the space used by these data structures, yielding O(E + n * (discounts + 1) + (discounts + 1) * E). Since E can be much larger than n and discounts, this simplifies to O(E * (discounts + 1)).

In summary:

  • Time Complexity: O((discounts + 1) * E * log((discounts + 1) * E))
  • Space Complexity: O(E * (discounts + 1))

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Shortest Path

Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ