55 lines
1.4 KiB
C++
55 lines
1.4 KiB
C++
|
#include<stdcpp.h>
|
||
|
|
using namespace std;
|
||
|
|
class Solution{
|
||
|
|
public:
|
||
|
|
int people_counter(
|
||
|
|
vector<vector<int> > nodes, int k, int prev, long long & ans, int seats
|
||
|
|
){
|
||
|
|
int people = 1;
|
||
|
|
for(int node : nodes[k]){
|
||
|
|
if(node == prev){continue;}
|
||
|
|
people+=people_counter(nodes,node,k, ans, seats);
|
||
|
|
}
|
||
|
|
if(k > 0)
|
||
|
|
ans += (people+seats - 1)/seats;
|
||
|
|
return people;
|
||
|
|
}
|
||
|
|
long long minimumFuelCost(vector<vector<int> >& roads, int seats){
|
||
|
|
vector<vector<int> >nodes(roads.size() + 1);
|
||
|
|
for(vector<int> edge: roads){
|
||
|
|
const int u = edge[0], v = edge[1];
|
||
|
|
nodes[u].push_back(v);
|
||
|
|
nodes[v].push_back(u);
|
||
|
|
}
|
||
|
|
long long ans = 0;
|
||
|
|
people_counter(nodes,0, -1, ans, seats);
|
||
|
|
cout<<ans<<endl;
|
||
|
|
return ans;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
int main(){
|
||
|
|
Solution sol;
|
||
|
|
vector<int> rd1 = {3,1};
|
||
|
|
vector<int> rd2 = {3,2};
|
||
|
|
vector<int> rd3 = {1,0};
|
||
|
|
vector<int> rd4 = {0,4};
|
||
|
|
vector<int> rd5 = {0,5};
|
||
|
|
vector<int> rd6 = {4,6};
|
||
|
|
vector<vector<int> >ex1 = {rd1,rd2,rd3,rd4,rd5,rd6};
|
||
|
|
sol.minimumFuelCost(ex1, 2);
|
||
|
|
|
||
|
|
rd1[0]=0; rd1[1] = 1;
|
||
|
|
rd2[0]=0; rd2[1] = 2;
|
||
|
|
rd3[0]=0; rd3[1] = 3;
|
||
|
|
vector<vector<int> >ex2 = {rd1,rd2,rd3};
|
||
|
|
|
||
|
|
sol.minimumFuelCost(ex2, 5);
|
||
|
|
|
||
|
|
vector<vector<int> >ex3 ;
|
||
|
|
sol.minimumFuelCost(ex3,1);
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
}
|