Leetcode-Daily-Challenge-/43_minfuel.cpp at main · coderbysoul/Leetcode-Daily-Challenge- · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    void countChild(int index, vector<vector<int>> &graph, vector<int> &child)
    {
        child[index]=1;

        for(auto &x: graph[index])
        {
            if(child[x]==0)
            {
                countChild(x,graph,child);
                child[index]+=child[x];
            }
        }

        return;
    }
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n=roads.size()+1;

        vector<vector<int>> graph(n);

        for(int i=0;i<n-1;i++)
        {
            graph[roads[i][0]].push_back(roads[i][1]);
            graph[roads[i][1]].push_back(roads[i][0]);
        }

        vector<int> child(n,0),vis(n,0);

        countChild(0,graph,child);

        queue<int> q;
        q.push(0);
        vis[0]=1;

        long long minFuel = 0;

        while(!q.empty())
        {
            int curr = q.front();
            q.pop();

            for(auto &x: graph[curr])
            {
                if(vis[x]==1)
                    continue;
                int cnt = child[x];
                minFuel+=cnt/seats;

                if(cnt%seats)
                    minFuel++;

                q.push(x);
                vis[x]=1;
            }
        }

        return minFuel;
    }
};