Minimum Cost to Buy Apples
Problem
You are given n cities numbered 1..n, a list of undirected roads where [a, b, w] means travelling between city a and city b costs w, an array appleCost where appleCost[i] is the price of one apple in city i+1, and an integer k. Starting from a city, every road you walk on the way out costs its weight, and every road on the way back costs k times its weight. For each starting city, find the minimum total cost to buy exactly one apple somewhere and return home. Return an array answer where answer[i] is that minimum for starting city i+1.
Buying at city j from start s costs appleCost[j] + (k + 1) · dist(s, j), since the round trip pays the road weights once on the way out and k times on the way back.
n = 4, roads = [[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]], appleCost = [56,42,102,301], k = 2[54, 42, 48, 51]import heapq
def min_cost(n, roads, apple_cost, k):
adj = [[] for _ in range(n + 1)]
for a, b, w in roads:
adj[a].append((b, w))
adj[b].append((a, w))
def dijkstra(src):
dist = [float('inf')] * (n + 1)
dist[src] = 0
pq = [(0, src)]
best = apple_cost[src - 1]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
best = min(best, apple_cost[u - 1] + (k + 1) * d)
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return best
return [dijkstra(s) for s in range(1, n + 1)]function minCost(n, roads, appleCost, k) {
const adj = Array.from({ length: n + 1 }, () => []);
for (const [a, b, w] of roads) {
adj[a].push([b, w]);
adj[b].push([a, w]);
}
function dijkstra(src) {
const dist = new Array(n + 1).fill(Infinity);
dist[src] = 0;
const pq = [[0, src]];
let best = appleCost[src - 1];
while (pq.length) {
pq.sort((x, y) => x[0] - y[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
best = Math.min(best, appleCost[u - 1] + (k + 1) * d);
for (const [v, w] of adj[u]) {
const nd = d + w;
if (nd < dist[v]) { dist[v] = nd; pq.push([nd, v]); }
}
}
return best;
}
const ans = [];
for (let s = 1; s <= n; s++) ans.push(dijkstra(s));
return ans;
}class Solution {
public int[] minCost(int n, int[][] roads, int[] appleCost, int k) {
List<int[]>[] adj = new List[n + 1];
for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
for (int[] r : roads) {
adj[r[0]].add(new int[]{ r[1], r[2] });
adj[r[1]].add(new int[]{ r[0], r[2] });
}
int[] ans = new int[n];
for (int s = 1; s <= n; s++) ans[s - 1] = dijkstra(s, n, adj, appleCost, k);
return ans;
}
private int dijkstra(int src, int n, List<int[]>[] adj, int[] appleCost, int k) {
long[] dist = new long[n + 1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
pq.add(new long[]{ 0, src });
long best = appleCost[src - 1];
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0]; int u = (int) top[1];
if (d > dist[u]) continue;
best = Math.min(best, appleCost[u - 1] + (long)(k + 1) * d);
for (int[] e : adj[u]) {
long nd = d + e[1];
if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new long[]{ nd, e[0] }); }
}
}
return (int) best;
}
}vector<int> minCost(int n, vector<vector<int>>& roads, vector<int>& appleCost, int k) {
vector<vector<pair<int,int>>> adj(n + 1);
for (auto& r : roads) {
adj[r[0]].push_back({ r[1], r[2] });
adj[r[1]].push_back({ r[0], r[2] });
}
auto dijkstra = [&](int src) -> long long {
vector<long long> dist(n + 1, LLONG_MAX);
dist[src] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.push({ 0, src });
long long best = appleCost[src - 1];
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
best = min(best, (long long)appleCost[u - 1] + (long long)(k + 1) * d);
for (auto& e : adj[u]) {
long long nd = d + e.second;
if (nd < dist[e.first]) { dist[e.first] = nd; pq.push({ nd, e.first }); }
}
}
return best;
};
vector<int> ans;
for (int s = 1; s <= n; s++) ans.push_back((int)dijkstra(s));
return ans;
}Explanation
The key observation is that the answer for a starting city only depends on the shortest road distance from that city to every other city. If the cheapest path from your start s to some city j has total road weight d, then a round trip pays those weights once going out and k times coming home, so the travel cost is (k + 1) · d. Add the local apple price and you get appleCost[j] + (k + 1) · d for buying at city j.
So for one starting city the whole problem reduces to: find the smallest value of appleCost[j] + (k + 1) · dist(s, j) over all cities j. The natural tool for "shortest distance to every node from one source" with non-negative weights is Dijkstra's algorithm.
We run Dijkstra once per starting city. Each time we settle a city u (pop it from the min-heap with its final distance d), we immediately evaluate the buy-here cost appleCost[u] + (k + 1) · d and keep a running minimum. Because Dijkstra settles cities in increasing distance order, every city gets evaluated exactly once with its true shortest distance.
Walk the example from city 1. Dijkstra settles city 1 at distance 0 (buy here = 56), then city 2 at distance 4 (buy here = 42 + 3·4 = 54), then city 3 at distance 4 (buy here = 102 + 12 = 114), then city 4 at distance 5 (buy here = 301 + 15 = 316). The smallest is 54, buying at city 2. Repeating from each start gives [54, 42, 48, 51].
Note the cost only ever increases with distance for a fixed apple price, but a far city can still win if its apple is cheap enough — that is exactly why we must check every settled city, not just the nearest one.