Minimum Apple Purchase Cost with Road Taxes
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Minimum Apple Purchase Cost with Road Taxes
There are `n` shops numbered `0` through `n - 1`. Buying apples at shop `i` costs `prices[i]`.
Each row `[u, v, cost, tax]` in `roads` describes a bidirectional road between shops `u` and `v`:
- Crossing it without apples costs `cost`.
- Crossing it while carrying apples costs `cost * tax`.
For each starting shop `i`, find the minimum total cost of obtaining apples and ending back at `i`. You may buy locally without traveling, or travel empty to another reachable shop `j`, buy there once, and return carrying the apples.
The outward and return routes may use different roads. A trip may use any number of roads, and each traversal is charged according to whether you are carrying apples. Return an array whose entry at index `i` is the minimum cost for starting shop `i`.
### Function
`vector<int> minCost(int n, vector<int>& prices, vector<vector<int>>& roads)`
### Example 1
**Input:** `n = 3, prices = [30, 25, 2], roads = [[0, 1, 1, 10], [1, 2, 1, 10], [0, 2, 5, 1]]`
**Output:** `[9, 13, 2]`
**Explanation:** The complete road information is:
| Connected shops | Empty cost | Tax multiplier | Cost with apples |
| --- | --- | --- | --- |
| `0` and `1` | `1` | `10` | `10` |
| `1` and `2` | `1` | `10` | `10` |
| `0` and `2` | `5` | `1` | `5` |
From shop `0`, go empty along `0 -> 1 -> 2` for `2`, buy for `2`, and return directly along `2 -> 0` for `5`. The total is `9`; the two routes are different. From shop `1`, go to shop `2` for `1`, buy for `2`, and return for `10`, totaling `13`. At shop `2`, buying locally costs `2`.
### Example 2
**Input:** `n = 4, prices = [7, 2, 9, 1], roads = [[0, 1, 2, 2], [2, 3, 3, 1]]`
**Output:** `[7, 2, 7, 1]`
**Explanation:** The road network has two disconnected pairs, `0 -- 1` and `2 -- 3`. From shop `0`, a purchase at shop `1` would cost `2 + 2 + 4 = 8`, so buying locally for `7` is better. From shop `2`, visiting shop `3` costs `3 + 1 + 3 = 7`, improving on its local price of `9`. Shops `1` and `3` buy locally.
### Constraints
- `1 <= n <= 1000`
- `prices.length == n`
- `1 <= prices[i] <= 1000000000`
- `0 <= roads.length <= min(n * (n - 1) / 2, 2000)`
- Every road has exactly four integers `[u, v, cost, tax]`.
- `0 <= u, v < n`, and `u != v`.
- `1 <= cost <= 1000000000`
- `1 <= tax <= 100`
- No pair of shops has more than one road between them.
### Clarifications
- The cost with apples is the full product `cost * tax`, not an extra surcharge added to `cost`.
- Both travel directions on a road use the same empty cost and the same multiplier.
- The road network need not be connected. Buying locally is always available.
- Each starting shop is an independent calculation; purchases do not change prices or roads.
### What a Strong Answer Covers
- Choosing both a purchase shop and complete outward and return routes.
- Allowing the two routes to differ when their travel costs differ.
- Handling disconnected shops and intermediate costs larger than a 32-bit integer.
Overview: Find the cheapest apple purchase round trip from every shop when road costs depend on whether apples are carried and the two travel routes may differ.
