LeetCode 2477: Minimum Fuel Cost to Report to the Capital
Problem Description
Explanation
To find the minimum fuel cost to report to the capital, we can use a depth-first search (DFS) approach starting from the capital city. At each step, we calculate the total fuel cost for all representatives to reach the current city considering the available seats in each car.
- We start from the capital city (city 0) and recursively explore all neighboring cities.
- For each neighbor, we calculate the total fuel cost to reach that city considering the representatives that can share the car.
- We continue this process until we reach all cities.
The time complexity of this approach is O(n), where n is the number of cities in the network. The space complexity is also O(n) for the recursive stack.
Solutions
class Solution {
public int minFuelCost(int[][] roads, int seats) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] road : roads) {
graph.computeIfAbsent(road[0], k -> new ArrayList<>()).add(road[1]);
graph.computeIfAbsent(road[1], k -> new ArrayList<>()).add(road[0]);
}
return dfs(0, -1, graph, seats);
}
private int dfs(int city, int parent, Map<Integer, List<Integer>> graph, int seats) {
int totalFuelCost = 0;
for (int neighbor : graph.getOrDefault(city, new ArrayList<>())) {
if (neighbor != parent) {
int childrenFuel = dfs(neighbor, city, graph, seats);
totalFuelCost += (childrenFuel + seats - 1) / seats;
}
}
return totalFuelCost;
}
}Loading editor...