Show problems as
Classic problem #2477MediumTreeDepth-First SearchBreadth-First SearchGraph Theory

Minimum Fuel Cost to Report to the Capital

Real-world version: Fuel to Bring Every Warden In
Tracked in this browser only
Read Minimum Fuel Cost to Report to the Capital on LeetCode(opens in a new tab)

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

A park has n depots numbered 0 through n - 1, joined by n - 1 two-way tracks. roads[i] = [a, b] is a track between depot a and depot b, and the layout is such that exactly one route of tracks joins any two depots.

One warden waits at every depot other than depot 0, and every warden must reach depot 0, where the ranger station stands. Each of those depots also holds one van, and a van carries at most seats wardens.

Wardens travel by van along the tracks. A van burns one litre of fuel for each track it drives along. Wardens may change vans freely whenever they meet at a depot, and a van may be abandoned at any depot.

Return the least fuel, in litres, that gets every warden to depot 0.

Examples

Example 1

Input
roads = [[0, 1], [0, 2], [0, 3]], seats = 5
Output
3

Each of the three wardens drives their own van straight along one track to depot 0, burning one litre each.

Example 2

Input
roads = [[0, 1], [1, 2], [2, 3], [3, 4]], seats = 2
Output
6

The depots form a line 0-1-2-3-4. The track between depots 3 and 4 is driven once, the one between 2 and 3 once, the one between 1 and 2 twice, and the one between 0 and 1 twice, for six litres in total.

Example 3

Input
roads = [[0, 1]], seats = 10
Output
1

A single warden drives one track, burning one litre.

Constraints

  • roads.length == 0 or roads.length >= 1
  • 1 <= roads.length <= 99999
  • roads[i].length == 2
  • 0 <= roads[i][0] <= 99999
  • 0 <= roads[i][1] <= 99999
  • The tracks join n = roads.length + 1 depots so that exactly one route links any two of them
  • 1 <= seats <= 10^5

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 total_fuel(roads: list[list[int]], seats: int) -> int:
Java
public long totalFuel(int[][] roads, int seats)

More on the same topics