2568. Minimum Fuel Cost to Report to the Capital
My accepted Python solution to LeetCode problem 2568, Minimum Fuel Cost to Report to the Capital, running in 221ms.
- Difficulty: Medium
- Python
- Runtime 221ms
- Memory 76MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 221ms, memory 76MB, accepted 2025-12-31.
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
from collections import defaultdict
if not roads:
return 0
# Build adjacency list
graph = defaultdict(list)
for a, b in roads:
graph[a].append(b)
graph[b].append(a)
self.fuel = 0
def dfs(node, parent):
# Returns number of people in subtree
people = 1 # Current representative
for neighbor in graph[node]:
if neighbor != parent:
people += dfs(neighbor, node)
# If not at capital, need to travel to parent
if node != 0:
# Number of cars needed = ceil(people / seats)
cars = (people + seats - 1) // seats
self.fuel += cars
return people
dfs(0, -1)
return self.fuel