2473. Minimum Cost to Buy Apples

MediumGraphArrayShortest PathHeap (Priority Queue)

Problem Description

The problem presents a scenario with n cities, where each city is assigned a number from 1 to n. There are bidirectional roads connecting some of the cities, and each road has a cost associated with traversing it. The cost of each road is given in a 2D array called roads, with each element being a triplet containing the starting city, the ending city, and the cost of the road between them.

Additionally, each city has a cost for purchasing apples, laid out in the array appleCost, where appleCost[i] represents the cost to buy an apple in the ith city.

The goal is to calculate the minimum total cost to start from each city, travel to any other city to buy exactly one apple, and then return to the starting city, taking into account that the cost of traveling on any road after purchasing the apple is multiplied by a factor k.

The challenge is to find the optimal route that minimizes the total cost of buying an apple and returning, considering both the initial travel costs to get to the city with the apple and the inflated costs for the return trip. The output is an array where each element represents the minimum total cost starting from city i.

Intuition

To solve this problem, we can use Dijkstra's algorithm, which is a famous graph search algorithm used to find the shortest path between nodes in a graph. It is especially useful when we have a graph with weighted edges, such as the road costs in our problem.

The approach is to run Dijkstra's algorithm from each city, considering that algorithm as the starting point. The algorithm maintains a priority queue of cities by the distance from the starting city and iteratively updates the distance of neighboring cities if a shorter path is found.

Here are the important components of the solution:

Priority Queue (Min Heap): This data structure is used to efficiently get the next city with the smallest cumulative road cost from the starting city.
Distance Array: An array to keep track of the minimum cost to travel from the starting city to every other city.
Graph Representation: The cities and roads are represented using a graph where each city is a node and each road is an edge connecting two nodes with a weight equal to the road cost.
Multiplication Factor k: This factor scales up the road costs after purchasing the apple. When calculating the minimum total cost from every city, the return cost must be the road cost multiplied by k plus the initial cost of getting to the apple-purchasing city.

The dijkstra() function is defined to calculate the minimum total cost to buy an apple starting from city i. This function uses a priority queue to find the shortest path from the starting city to all cities where apples can be purchased, considering the increased cost of return.

The solution uses a modified Dijkstra's algorithm that keeps track of the total cost, which includes the apple's cost and both outbound and return trip costs. The final total cost is determined by the sum of the cost to reach the apple-selling city, the cost of the apple, and the return cost to the starting city (scaled by k).

Lastly, we iterate over every city and call the dijkstra() function to get the array of minimum costs when starting from each city. This array is the desired output of the problem.

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

Solution Approach

The solution to the problem uses Dijkstra's algorithm, which is applied to each city to find the minimum cost to buy an apple and return. Let's dissect the solution and understand how it's implemented:

Graph Representation: Before running Dijkstra's, we need to represent the cities and roads as a graph. This is done using a dictionary, where the dictionary's key represents a city, and the value is a list of tuples with each tuple containing a neighboring city and the cost of the road to that city. This is generated from the roads input array by adjusting the city indices to be zero-based (as Python uses zero-based indexing) and by treating the roads as bidirectional.
Priority Queue (Heap): A heap is used as a priority queue to keep track of which city should be visited next based on the current cost. Python's heapq library provides the functionality for the heap data structure, and heappush is used to add a city to the heap, and heappop to remove the city with the minimum cost.
Dijkstra's Algorithm: For each city, we apply Dijkstra's algorithm to find the shortest paths to all other cities. We maintain a dist array to store the minimum cost to reach each city from the starting city. This array is initialized with inf (infinity) since initially, we don't know the minimum cost. As we explore the graph, we update this array with the actual minimum cost when a cheaper path is found. If a shorter path to a city is discovered, we update the dist for that city and push it onto the heap for further exploration.

The dijkstra() helper function computes the minimum cost to purchase an apple and return when starting at city i. It initializes the priority queue and the distance array and sets the starting city's distance to 0. As it processes cities from the priority queue, it checks and updates the distances of neighboring cities (those directly connected via a road) if the current distance is less. It also calculates the minimum total cost by considering the cost of buying an apple from the current city plus the cost of the path from the starting city multiplied by factor k + 1.

Cost Calculation: The cost of buying an apple and returning is computed for each city by starting the Dijkstra's algorithm from that city. The minimum total cost includes the cost of the travel to the city with the apple (obtained from running Dijkstra's), the cost of the apple itself, and the cost of returning to the starting city. For the return cost, we multiply the path cost by k, and this is accounted for each time we compute the minimum total cost during the execution of the algorithm.
Result Array: After computing the minimum total cost for each starting city, we store the results in an array. The final output is generated by running the dijkstra() function for every city i in the range from 0 to n - 1, and populating the resulting minimum costs in an array that is returned.

Ultimately, the approach is to iteratively apply Dijkstra's algorithm for each city and use the total cost formula which includes the cost of an apple and the path costs (both to and from the city where the apple is bought, with the return cost being scaled by factor k) to find the minimum total cost when starting from each city.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to help illustrate how the solution approach is applied.

Suppose there are n = 3 cities, with the following roads and appleCost:

roads = [[1, 2, 5], [2, 3, 5], [1, 3, 2]]
appleCost = [4, 2, 1]
k = 2

Firstly, we will prepare the graph representation. Cities are numbered starting from 1, hence we subtract 1 from each to convert to zero-based indexing:

The graph will be represented as an adjacency list: { 0: [(1, 5), (2, 2)], 1: [(0, 5), (2, 5)], 2: [(0, 2), (1, 5)] }

Now, we need to calculate the minimum total cost for each city using the Dijkstra's algorithm.

Running Dijkstra's from city 0:

Initially, the distance array is [0, inf, inf] (the cost to reach the starting city from itself is always 0).
The heap will start with only the starting city: [(0, 0)] (cost, city).
The distances to the neighboring cities are updated as we pop from the heap: dist[1] will become 5, and dist[2] will become 2.
Apple costs are then added to the shortest path costs, and the cost for the return is multiplied by k, resulting in total costs: [4, 10*2 + 2, 1*2 + 1] = [4, 22, 3].

Running Dijkstra's from city 1:

Distance array starts as [inf, 0, inf].
Heap starts as [(0, 1)].
The distances will be updated to [5, 0, 5].
Total costs will be: [5*2 + 4, 2, 5*2 + 1] = [14, 2, 11].

Running Dijkstra's from city 2:

Distance array starts as [inf, inf, 0].
Heap starts as [(0, 2)].
Distances are updated to [2, 5, 0].
Total costs: [2*2 + 4, 5*2 + 2, 1] = [8, 12, 1].

Finally, we take the minimum total cost for each starting city which is [4, 2, 1].

The final output array for the minimum total cost starting from each city i is therefore [4, 2, 1].

Solution Implementation

1from typing import List
2from heapq import heappop, heappush
3from collections import defaultdict
4from math import inf
5
6class Solution:
7    # Function to find minimum cost to buy apples from different towns
8    def minCost(self, towns: int, roads: List[List[int]], appleCosts: List[int], multiplier: int) -> List[int]:
9      
10        # Implementation of Dijkstra's algorithm to find minimum cost from a town
11        def dijkstra(start_index):
12            # Priority queue to determine which town to visit next, based on the accumulated cost
13            priority_queue = [(0, start_index)]
14          
15            # Array to track the minimum distance from the start_index to every other town
16            min_distances = [inf] * towns
17            min_distances[start_index] = 0
18          
19            # Initialize answer as infinity
20            min_cost = inf
21          
22            # Loop until there are towns in the priority queue
23            while priority_queue:
24                # Get the current distance and town index with the lowest cost
25                current_distance, current_town = heappop(priority_queue)
26              
27                # Update the min_cost considering the cost of apples and transportation
28                min_cost = min(min_cost, appleCosts[current_town] + current_distance * (multiplier + 1))
29              
30                # Explore all connected towns
31                for adjacent_town, road_cost in graph[current_town]:
32                    if min_distances[adjacent_town] > min_distances[current_town] + road_cost:
33                        # Update the distance to adjacent_town
34                        min_distances[adjacent_town] = min_distances[current_town] + road_cost
35                        # Add adjacent_town to priority queue with updated cost
36                        heappush(priority_queue, (min_distances[adjacent_town], adjacent_town))
37          
38            return min_cost
39      
40        # Initialize graph as a dictionary of lists to hold all roads between the towns
41        graph = defaultdict(list)
42      
43        # Construct the graph
44        for road_start, road_end, road_cost in roads:
45            # Adjust indices to be zero-based
46            road_start, road_end = road_start - 1, road_end - 1 
47            # Add both directions since the roads are bidirectional
48            graph[road_start].append((road_end, road_cost))
49            graph[road_end].append((road_start, road_cost))
50      
51        # Compute and return the minimum cost from each town using Dijkstra's algorithm
52        return [dijkstra(i) for i in range(towns)]
53

1class Solution {
2    private int maxDistance; // 'k' is renamed to 'maxDistance' for better clarity.
3    private int[] appleCost; // Cost to pick apples in each city.
4    private int[] distances; // Distances from the starting city.
5    private List<int[]>[] graph; // Graph representation where each city has a list of edges.
6    private static final int INFINITY = 0x3f3f3f3f; // Represents an infinite distance.
7
8    // Calculates the minimum cost to collect apples from different cities, given certain conditions.
9    public long[] minCost(int numCities, int[][] roads, int[] appleCost, int maxDistance) {
10        this.appleCost = appleCost;
11        this.maxDistance = maxDistance;
12        graph = new List[numCities];  // Initialize graph for the given number of cities.
13        distances = new int[numCities]; // Initialize distances array.
14      
15        // Initialize graph with empty lists for each city.
16        for (int i = 0; i < numCities; ++i) {
17            graph[i] = new ArrayList<>();
18        }
19      
20        // Build the graph with the given road information.
21        for (int[] road : roads) {
22            int cityA = road[0] - 1;
23            int cityB = road[1] - 1;
24            int cost = road[2];
25            graph[cityA].add(new int[] {cityB, cost});
26            graph[cityB].add(new int[] {cityA, cost});
27        }
28      
29        // Calculate minimum cost for each city.
30        long[] minCosts = new long[numCities];
31        for (int cityIndex = 0; cityIndex < numCities; ++cityIndex) {
32            minCosts[cityIndex] = dijkstra(cityIndex);
33        }
34        return minCosts;
35    }
36
37    // Helper method to perform Dijkstra's algorithm to find the shortest paths and minimum cost from a city.
38    private long dijkstra(int startCity) {
39        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
40        priorityQueue.offer(new int[] {0, startCity});
41        Arrays.fill(distances, INFINITY);
42        distances[startCity] = 0;
43        long minCost = Long.MAX_VALUE;
44      
45        while (!priorityQueue.isEmpty()) {
46            int[] current = priorityQueue.poll();
47            int currentDistance = current[0];
48            int currentCity = current[1];
49            minCost = Math.min(minCost, (long) appleCost[currentCity] + ((long) maxDistance + 1) * currentDistance);
50          
51            for (int[] neighbor : graph[currentCity]) {
52                int neighborCity = neighbor[0];
53                int edgeWeight = neighbor[1];
54                if (distances[neighborCity] > distances[currentCity] + edgeWeight) {
55                    distances[neighborCity] = distances[currentCity] + edgeWeight;
56                    priorityQueue.offer(new int[] {distances[neighborCity], neighborCity});
57                }
58            }
59        }
60      
61        return minCost;
62    }
63}
64

1#include <vector>
2#include <queue>
3#include <cstring>
4#include <climits>
5
6using std::vector;
7using std::pair;
8using std::priority_queue;
9using std::min;
10using ll = long long;
11using Pii = pair<int, int>;
12
13class Solution {
14public:
15    // Use a constant to represent infinity.
16    const int INF = 0x3f3f3f3f;
17
18    // Function to calculate the minimum cost to get apples from cities considering transportation cost.
19    vector<ll> minCost(int n, vector<vector<int>>& roads, vector<int>& appleCost, int k) {
20        // Graph representation: each city's adjacency list with (neighboring city, cost).
21        vector<vector<Pii>> graph(n);
22        // Build bidirectional edges for the undirected roads graph.
23        for (auto& road : roads) {
24            int from = road[0] - 1; // Assuming 1-indexed cities adjusting to 0-indexed.
25            int to = road[1] - 1;
26            int cost = road[2];
27            graph[from].emplace_back(to, cost);
28            graph[to].emplace_back(from, cost);
29        }
30      
31        // Distance vector to store minimum distance to each city.
32        vector<int> dist(n, INF);
33
34        // Dijkstra algorithm lambda function.
35        auto dijkstra = [&](int startCity) {
36            // Reset distances to INF.
37            std::fill(dist.begin(), dist.end(), INF);
38            // Priority queue for minimum distance.
39            priority_queue<Pii, vector<Pii>, std::greater<Pii>> queue;
40            queue.push({0, startCity});
41            dist[startCity] = 0;
42            ll minCostPrev = LLONG_MAX;
43            while (!queue.empty()) {
44                auto [curDist, curCity] = queue.top();
45                queue.pop();
46                // Compute cost with apple cost, considering (k+1) trips needed.
47                minCostPrev = min(minCostPrev, appleCost[curCity] + static_cast<ll>(curDist) * (k + 1));
48                for (auto& [nextCity, edgeCost] : graph[curCity]) {
49                    if (dist[nextCity] > dist[curCity] + edgeCost) {
50                        dist[nextCity] = dist[curCity] + edgeCost;
51                        queue.push({dist[nextCity], nextCity});
52                    }
53                }
54            }
55            return minCostPrev;
56        };
57
58        // Calculate minimum costs for apples for all cities.
59        vector<ll> minAppleCosts(n);
60        for (int i = 0; i < n; ++i) {
61            minAppleCosts[i] = dijkstra(i);
62        }
63        return minAppleCosts;
64    }
65};
66

1type Pair<T1, T2> = [T1, T2];
2type Graph = Pair<number, number>[][];
3
4const INF: number = 0x3f3f3f3f;
5type PriorityQueueItem = Pair<number, number>;
6class PriorityQueue {
7    private data: PriorityQueueItem[] = [];
8
9    public push(item: PriorityQueueItem): void {
10        this.data.push(item);
11        this.data.sort((a, b) => a[0] - b[0]);
12    }
13
14    public pop(): PriorityQueueItem | undefined {
15        return this.data.shift();
16    }
17
18    public isEmpty(): boolean {
19        return this.data.length === 0;
20    }
21}
22
23function minCost(n: number, roads: number[][], appleCost: number[], k: number): number[] {
24    const graph: Graph = Array.from({ length: n }, () => []);
25
26    roads.forEach((road) => {
27        const from = road[0] - 1;
28        const to = road[1] - 1;
29        const cost = road[2];
30        graph[from].push([to, cost]);
31        graph[to].push([from, cost]);
32    });
33
34    const dist: number[] = Array(n).fill(INF);
35
36    function dijkstra(startCity: number): number {
37        dist.fill(INF);
38        const queue = new PriorityQueue();
39        queue.push([0, startCity]);
40        dist[startCity] = 0;
41        let minCostPrev: number = Number.MAX_SAFE_INTEGER;
42        while (!queue.isEmpty()) {
43            const [curDist, curCity] = queue.pop()!;
44            minCostPrev = Math.min(minCostPrev, appleCost[curCity] + curDist * (k + 1));
45            graph[curCity].forEach(([nextCity, edgeCost]) => {
46                if (dist[nextCity] > dist[curCity] + edgeCost) {
47                    dist[nextCity] = dist[curCity] + edgeCost;
48                    queue.push([dist[nextCity], nextCity]);
49                }
50            });
51        }
52        return minCostPrev;
53    }
54
55    return Array.from({ length: n }, (_, i) => dijkstra(i));
56}
57

Time and Space Complexity

Time Complexity

The time complexity of the given code is dominated by the Dijkstra algorithm which is executed for each node i in the range [0, n). The Dijkstra algorithm, in its standard form, has a time complexity of O(E + V log V) where E is the number of edges and V is the number of vertices in the graph, as it uses a min-heap (priority queue) to efficiently retrieve the closest unvisited node at each step. In this case, since Dijkstra's algorithm is run for every node in the graph, the overall time complexity becomes O(n * (E + n log n)).

Space Complexity

The space complexity is determined by the space needed to store the graph, the distance array dist, and the priority queue q. The graph g is a dictionary of adjacency lists, which will take up O(E) space, where E is again the number of edges. The distance array dist will take O(n) space and will be created n times. However, the space due to dist is reused for each call of dijkstra, so additional space is not accumulated for each call. The priority queue q will at maximum contain all the vertices, so it will take O(n) space.

Therefore, the overall space complexity is O(E + n). Notably, even though the distance array is created n times, it does not add to the space complexity because it does not exist simultaneously for all those instances.

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

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

Question 1 out of 10

Which of the following array represent a max heap?

20 12 16 1 2 3 4

20 30 10 5 6 7 18

30 20 11 2 3 4 12

50 30 40 10 20 30 40

I don’t know