Minimum Cost to Buy Apples II
You are given an integer n and an integer array prices of length n, where prices[i] is the price of apples at shop i.
You are also given a 2D integer array roads, where roads[i] = [ui, vi, costi, taxi] represents a bidirectional road:
uiandviare the shops connected by the road.costiis the cost to travel the road without carrying apples.taxiis the multiplier applied tocostiwhen traveling with apples.
For each shop i, you can either:
- Buy apples locally at shop
iforprices[i]. - Travel empty to any shop
jusing any number of roads, buy apples forprices[j], and return to shopiwhile carrying apples, payingcost * taxon each road used for the return trip.
The forward path, where you travel empty, and the return path may be different.
Return an integer array ans of length n, where ans[i] is the minimum total cost to buy apples starting from shop i.
Example 1
Input
n = 2, prices = [8,3], roads = [[0,1,1,2]]Output
[6,3]From shop 0, traveling to shop 1 and returning costs 1 + 2 + 3 = 6, while shop 1 is cheapest by buying locally for 3.
Example 2
Input
n = 3, prices = [9,4,6], roads = [[0,1,1,3],[1,2,4,2]]Output
[8,4,6]Shop 0 can buy via shop 1 for total cost 8, while shops 1 and 2 are cheapest by buying locally for 4 and 6.
Constraints
- 1 <= n <= 1000
- prices.length == n
- 1 <= prices[i] <= 10^9
- 0 <= roads.length <= min(n × (n - 1) / 2, 2000)
- roads[i] = [ui, vi, costi, taxi]
- 0 <= ui, vi <= n - 1
- ui != vi
- 1 <= costi <= 10^9
- 1 <= taxi <= 100
- There are no repeated edges.