Minimum Cost to Buy Apples II - Solution & Explanation

Problem Overview: You are given multiple cities connected by roads with travel costs. Each city sells apples at a different price. Starting from any city, you may travel to another city to buy apples and then return. The goal is to compute the minimum total cost (travel + apple price) for each starting city.

Approach 1: Brute Force with All-Pairs Shortest Paths (Floyd–Warshall) (Time: O(n^3), Space: O(n^2))

Compute the shortest distance between every pair of cities using the Floyd–Warshall algorithm. Once all distances are known, iterate through every pair (start, buyCity) and compute the total cost: travel to the city, buy the apple, and return. This approach is straightforward but expensive. With large graphs, the O(n^3) preprocessing dominates runtime and quickly becomes impractical.

Approach 2: Run Dijkstra from Every City (Time: O(n * (m log n)), Space: O(n + m))

Instead of computing all-pairs distances, run graph shortest path from each starting city using Dijkstra's algorithm. The shortest distance to every other city is computed in O(m log n). For each reachable city, calculate the total purchase cost: dist[start][j] + appleCost[j] + returnCost. Repeating this for all starting cities yields the correct answer while avoiding the cubic complexity of Floyd–Warshall.

Approach 3: Optimized Multi-Source Dijkstra (Time: O(m log n), Space: O(n + m))

The optimal solution flips the perspective. Instead of evaluating every start city separately, treat each apple city as a potential source with an initial cost equal to its apple price. Run a multi-source shortest path computation. During relaxation, propagate travel costs through the graph so each node discovers the cheapest place to buy apples. This works because Dijkstra naturally expands the minimum-cost frontier, combining purchase price and travel cost in a single pass.

Recommended for interviews: Start by explaining the brute-force idea with all-pairs distances to demonstrate the correct cost formula. Then move to the Dijkstra-based solution. Interviewers usually expect the optimized shortest-path approach since it reduces the complexity to roughly O(m log n), which scales well for large road networks.