class Solution {
public:
vector<vector<int>> graph;
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
graph.resize(roads.size() + 1);

for(auto& v: roads) {
graph[v[0]].push_back(v[1]);
graph[v[1]].push_back(v[0]);
}

queue<pair<int,int>> q;
queue<int> leaf;
vector<long long> distance(roads.size() + 1, 1e9);
vector<int> numPerson(roads.size() + 1, 1);
q.push({0, 0});
distance[0] = 0;
while(!q.empty()) {
auto [node, d] = q.front();
q.pop();
if(graph[node].size() == 1) {
leaf.push(node);
}
for(int i = 0 ;i < graph[node].size(); i++) {
int nextnode = graph[node][i];
if(distance[nextnode] == 1e9) {
distance[nextnode] = d + 1;
q.push({nextnode, d + 1});
}
}
}
long long ret = 0;
while(!leaf.empty()) {
auto node = leaf.front();
leaf.pop();

if (node == 0) {
continue;
}
if(numPerson[node] >= seats) {
int numCar = numPerson[node]/seats;
numPerson[node]%= seats;
ret += numCar*distance[node];
}
// 이동
int idx = graph[node][0];
graph[idx].erase(remove(graph[idx].begin(), graph[idx].end(), node), graph[idx].end());
if(numPerson[node] != 0)
ret++;
numPerson[idx] += numPerson[node];
if(graph[idx].size() == 1) {
leaf.push(idx);
}
}
return ret;
}
};

문제를 복잡하게 풀었다..
bfs로 거리 측정, 잎 큐에넣고
잎제거하면서 차태워보냄