leetcode

0 class Solution {

1 public:

2 long long minimumFuelCost(vector<vector<int>> &roads, int seats) {

3 int n = roads.size() + 1;

4 vector<vector<int>> adj(n, vector<int>());

5 vector<int> count(n, 0);

6 stack<pair<int, int>> st;

7

8 for (auto &p : roads) {

9 adj[p[0]].push_back(p[1]);

10 adj[p[1]].push_back(p[0]);

11 }

12

13 long long total = 0;

14 st.push({0, -1});

15 while (!st.empty()) {

16 auto [root, parent] = st.top();

17 st.pop();

18 if (parent == -2) {

19 for (int c : adj[root]) {

20 count[root] += count[c];

21 total += ceil(1.0 * count[c] / seats);

22 }

23 count[root]++;

24 continue;

25 }

26 st.push({root, -2});

27 for (int c : adj[root])

28 if (c != parent) st.push({c, root});

29 }

30 return total;

31 }

32 };