aboutsummaryrefslogtreecommitdiff
path: root/min_fuel_report_captial.cpp
blob: 5d13beb8b09e1e659345fa0532aa300f87af0a64 (plain)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 2477. Minimum Fuel Cost to Report to the Capital
#include "leetcode.h"

/*
 * there is a tree (ie. a connected, undirected graph with no cycles) structure
 * country network consisting of 'n' cities numbered from 0 to 'n - 1' and
 * exactly 'n - 1' roads the capital city is city 0. given a 2d integer array
 * 'roads' where 'roads[i] = [ai, bi]' denotes that there exists a bidirectional
 * road connecting cities ai & bi. there is a meeting for the representitive of
 * each city. the meeting is in the capital city. there is a car in each city.
 * given integer seats that indicates the number of seats in each car. a
 * representitive can use the car in their city to travel or change the car and
 * ride with another representitive. the cost of traveling between two cities is
 * 1 liter of fuel. return minimum number of liters of fuel needed to reach
 * capital city.
 */

class Solution {
public:
  long long minimumFuelCost(vvd(int) & roads, int seats) {
    vvd(int) al(roads.size() + 1);
    for (auto &r : roads) {
      al[r[0]].push_back(r[1]);
      al[r[1]].push_back(r[0]);
    }
    long long ans = 0;
    return dfs(0, -1, 0, seats, al, ans);
  }

private:
  long long dfs(int i, int prev, int depth, int seats, vvd(int) & al,
                long long &ans) {
    long long riders = 1;
    for (int j : al[i])
      if (j != prev)
        riders += dfs(j, i, depth + 1, seats, al, ans);
    if (depth == 0)
      return ans;
    ans += (riders / seats) * depth + (riders % seats ? 1 : 0);
    return riders % seats;
  }
};

int main() {
  Solution obj;
  vvd(int) roads1 = {{0, 1}, {0, 2}, {0, 3}};
  vvd(int) roads2 = {{3, 1}, {3, 2}, {1, 0}, {0, 4}, {0, 5}, {4, 6}};
  cout << obj.minimumFuelCost(roads1, 5) << endl; // expect: 3
  cout << obj.minimumFuelCost(roads2, 2) << endl; // expect: 7
}