1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public long minimumFuelCost(int[][] roads, int seats) {
Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
for (int[] road : roads) {
nodeNeighbors.computeIfAbsent(road[0], (key) -> new ArrayList<>()).add(road[1]);
nodeNeighbors.computeIfAbsent(road[1], (key) -> new ArrayList<>()).add(road[0]);
}
return minimumLiters(0, -1, nodeNeighbors, seats)[0];
}
private long[] minimumLiters(int node, int parent, Map<Integer, List<Integer>> nodeNeighbors, int seats) {
if (!nodeNeighbors.containsKey(node)) {
return new long[] { 0, 1 };
}
long literCount = 0, peopleCount = 1;
for (int neighbor : nodeNeighbors.get(node)) {
if (neighbor == parent)
continue;
long[] neighborInfo = minimumLiters(neighbor, node, nodeNeighbors, seats);
long carNeeded = neighborInfo[1] % seats == 0 ? neighborInfo[1] / seats : neighborInfo[1] / seats + 1;
literCount += neighborInfo[0] + carNeeded;
peopleCount += neighborInfo[1];
}
return new long[] { literCount, peopleCount };
}
}
|
