0936HardArrayGraph TheoryHeap (Priority Queue)Shortest Path

Cheapest Round Trip for One Crate

Tracked in this browser only

Trains the technique from

LeetCode 3928Minimum Cost to Buy Apples II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O((n + e) log n) for n depots and e roads: one Dijkstra over the rewritten graph.Space O(n + e) for the graph.

Because the drive home retraces the drive out, a road used on the trip is paid for twice over, once at its cost and once at its cost times its tax, so the whole road is worth one fixed amount: its cost times one more than its tax. Rewriting every road with that single weight turns the round trip into a one-way distance. A trip is then a distance from the starting depot to wherever the crate is bought, plus that depot's price. Rather than working that out for each start against every possible buying depot, add one imaginary depot joined to every real one by a road weighing exactly that depot's price. The cheapest trip from any depot is then simply its distance to the imaginary depot, so one run of Dijkstra out from it answers every depot at once.

Pythonentry point: min_cost

def min_cost(n, prices, roads):
    import heapq
    adj = [[] for _ in range(n + 1)]
    for u, v, cost, tax in roads:
        weight = cost * (tax + 1)
        adj[u].append((v, weight))
        adj[v].append((u, weight))
    source = n
    for i in range(n):
        adj[source].append((i, prices[i]))
        adj[i].append((source, prices[i]))
    INF = float("inf")
    best = [INF] * (n + 1)
    best[source] = 0
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > best[node]:
            continue
        for nxt, weight in adj[node]:
            step = d + weight
            if step < best[nxt]:
                best[nxt] = step
                heapq.heappush(heap, (step, nxt))
    return [best[i] for i in range(n)]

The obvious version

Work out every depot-to-depot distance over the rewritten roads by relaxing all pairs against all middle depots, then for each starting depot try every buying depot and keep the cheapest total. Cubic in the depot count and it uses no imaginary depot.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost(n, prices, roads):
    INF = float("inf")
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, cost, tax in roads:
        weight = cost * (tax + 1)
        if weight < dist[u][v]:
            dist[u][v] = weight
            dist[v][u] = weight
    for mid in range(n):
        for i in range(n):
            if dist[i][mid] == INF:
                continue
            for j in range(n):
                step = dist[i][mid] + dist[mid][j]
                if step < dist[i][j]:
                    dist[i][j] = step
    out = []
    for i in range(n):
        best = INF
        for j in range(n):
            if dist[i][j] == INF:
                continue
            here = dist[i][j] + prices[j]
            if here < best:
                best = here
        out.append(best)
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in