Show problems as
Classic problem #3928HardArrayGraph TheoryHeap (Priority Queue)Shortest Path

Minimum Cost to Buy Apples II

Real-world version: Cheapest Round Trip for One Crate
Tracked in this browser only
Read Minimum Cost to Buy Apples II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A region has n depots numbered from 0, and depot i sells a crate for prices[i].

Each entry of roads is [u, v, cost, tax] for a two-way road. Driving that road outward costs cost, and driving it back costs cost * tax.

Starting from a depot, you drive to any depot, buy exactly one crate there, and drive home along the very same roads you came by. Buying at home is allowed and costs no driving at all.

Return, for each depot in turn, the least a round trip can cost.

Examples

Example 1

Input
n = 4, prices = [27, 9, 41, 14], roads = [[0, 1, 3, 2], [1, 2, 4, 1], [2, 3, 2, 3]]
Output
[18, 9, 17, 14]

Each road is worth its cost times one more than its tax, so the three roads weigh 9, 8 and 8. From depot 0 the cheapest trip drives to depot 1 for 9 and buys at 9, coming to 18, which beats buying at home for 27.

Example 2

Input
n = 2, prices = [5, 100], roads = []
Output
[5, 100]

With no roads at all, every depot can only buy at home.

Example 3

Input
n = 3, prices = [10, 10, 10], roads = [[0, 1, 1, 100], [1, 2, 1, 100]]
Output
[10, 10, 10]

Every depot sells at the same price and the roads are heavily taxed, so no trip beats buying at home.

Constraints

  • 1 <= n <= 1000
  • prices.length == n
  • 1 <= prices[i] <= 10^9
  • 0 <= roads.length <= 2000
  • roads[i].length == 4
  • 0 <= roads[i][0] <= n - 1
  • 0 <= roads[i][1] <= n - 1
  • The two depots on a road are different
  • 1 <= roads[i][2] <= 10^9
  • 1 <= roads[i][3] <= 100
  • No road is listed twice

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_cost(n: int, prices: list[int], roads: list[list[int]]) -> list[int]:
Java
public int[] minCost(int n, int[] prices, int[][] roads)

More on the same topics