LeetCode 3928 - Minimum Cost to Buy Apples II

Difficulty: 🔴 Hard
Topics: Array, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

The problem asks us to determine the minimum cost to purchase apples starting from each shop, taking into account two types of costs: the local price of apples at each shop and the transportation costs along roads connecting the shops. Each road has a base cost to traverse when empty and a tax multiplier applied to the base cost when carrying apples. You can travel empty from your starting shop to any other shop, buy apples there, and return along potentially different roads while paying the "with apples" cost.

The inputs are:

n, the number of shops.
prices, a list of integers representing the local price of apples at each shop.
roads, a list of 4-element arrays [u, v, cost, taxi] describing bidirectional roads between shops u and v. Traveling empty along this road costs cost, and traveling with apples costs cost * taxi.

The output is an array of length n, where ans[i] represents the minimum cost to acquire apples starting from shop i, either by buying locally or traveling to another shop.

Constraints indicate:

Up to 1000 shops and 2000 roads, so an $O(n^2)$ approach is likely feasible but anything exponential is not.
Costs and taxes can be large (up to $10^9$ and 100), so integer overflow should be considered in languages like Go.
Roads are unique and bidirectional.

Edge cases include shops with no roads, single-shop scenarios, and cases where buying locally is cheaper than any travel option.

Approaches

Brute Force

The brute-force solution involves evaluating every possible path from shop i to every other shop j and computing the total cost for traveling empty to j and returning with apples. You would also compare this total cost to the local price at i. This guarantees correctness but is computationally expensive because the number of possible paths grows exponentially with the number of shops, making it impractical for $n=1000$.

Optimal Approach

The key observation is that the problem is essentially a shortest path problem on a weighted graph with two types of weights: empty travel and travel with apples. For each shop i, the minimum cost is the minimum of prices[i] and prices[j] + shortest_path(i -> j empty) + shortest_path(j -> i with apples).

To compute shortest paths efficiently, we can use Dijkstra's algorithm:

Construct two adjacency lists: one for empty travel costs and one for "with apples" costs (edge cost multiplied by tax).
For each shop i, perform Dijkstra to compute the shortest empty travel distance to all other shops.
Perform Dijkstra from all other shops j using "with apples" costs to compute the shortest return paths to shop i. This can be efficiently achieved by reversing the edges and running Dijkstra once per shop.
Combine the distances with the apple prices to compute the minimum cost.

This reduces the complexity from exponential to $O(n \cdot (m + n) \log n)$, which is feasible given the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Try all paths between shops
Optimal	O(n * (m + n) log n)	O(n + m)	Use Dijkstra twice per shop (empty and with apples)

Algorithm Walkthrough

Construct two adjacency lists: graph_empty using the costi values, and graph_with using costi * taxi.
For each shop i, initialize a result ans[i] as prices[i].
Run Dijkstra from i on graph_empty to get the shortest distances to all other shops when traveling empty.
For each shop j, compute the shortest return path to i using graph_with with Dijkstra (or by reversing edges and using a single run for all i).
For each j, compute the total cost as dist_empty[j] + dist_with[j] + prices[j] and update ans[i] with the minimum between current ans[i] and this total.
Repeat for all shops.

Why it works: The two Dijkstra runs guarantee that we compute the minimal travel cost from i to j and back under the two different edge weight regimes. By adding the local apple price, we cover all valid purchase paths. The minimum operation ensures we select the cheapest option.

Python Solution

from typing import List
import heapq

class Solution:
    def minCost(self, n: int, prices: List[int], roads: List[List[int]]) -> List[int]:
        from collections import defaultdict

        def dijkstra(start: int, graph: List[List[List[int]]]) -> List[int]:
            dist = [float('inf')] * n
            dist[start] = 0
            heap = [(0, start)]
            while heap:
                d, u = heapq.heappop(heap)
                if d > dist[u]:
                    continue
                for v, w in graph[u]:
                    if dist[v] > d + w:
                        dist[v] = d + w
                        heapq.heappush(heap, (dist[v], v))
            return dist

        # Build graphs
        graph_empty = [[] for _ in range(n)]
        graph_with = [[] for _ in range(n)]
        for u, v, cost, taxi in roads:
            graph_empty[u].append((v, cost))
            graph_empty[v].append((u, cost))
            graph_with[u].append((v, cost * taxi))
            graph_with[v].append((u, cost * taxi))

        ans = [0] * n
        for i in range(n):
            dist_empty = dijkstra(i, graph_empty)
            dist_with = dijkstra(i, graph_with)
            min_cost = prices[i]
            for j in range(n):
                total = dist_empty[j] + dist_with[j] + prices[j]
                if total < min_cost:
                    min_cost = total
            ans[i] = min_cost
        return ans

The Python code first builds two separate graphs for empty and loaded travel costs. The dijkstra function calculates the shortest distances. For each shop, we compute the minimal cost to acquire apples, either locally or by traveling to another shop and returning with apples.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to, cost int
}

type Item struct {
	node, dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return item
}

func dijkstra(n int, start int, graph [][]Edge) []int {
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt64
	}
	dist[start] = 0
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{start, 0})
	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Item)
		if cur.dist > dist[cur.node] {
			continue
		}
		for _, e := range graph[cur.node] {
			if dist[e.to] > cur.dist + e.cost {
				dist[e.to] = cur.dist + e.cost
				heap.Push(pq, Item{e.to, dist[e.to]})
			}
		}
	}
	return dist
}

func minCost(n int, prices []int, roads [][]int) []int {
	graphEmpty := make([][]Edge, n)
	graphWith := make([][]Edge, n)
	for _, r := range roads {
		u, v, cost, taxi := r[0], r[1], r[2], r[3]
		graphEmpty[u] = append(graphEmpty[u], Edge{v, cost})
		graphEmpty[v] = append(graphEmpty[v], Edge{u, cost})
		graphWith[u] = append(graphWith[u], Edge{v, cost * taxi})
		graphWith[v] = append(graphWith[v], Edge{u, cost * taxi})
	}

	ans := make([]int, n)
	for i := 0; i < n; i++ {
		distEmpty := dijkstra(n, i, graphEmpty)
		distWith := dijkstra(n, i, graphWith)
		minCost := prices[i]
		for j := 0; j < n; j++ {
			total := distEmpty[j] + distWith[j] + prices[j]
			if total < minCost {
				minCost = total
			}
		}
		ans[i] = minCost
	}
	return ans
}

The Go solution mirrors the Python approach but uses slices and a custom priority queue implementation. It handles large numbers safely using math.MaxInt64.

Worked Examples

Example 1

Input: `n=2, prices=[8,3], roads