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로 거리 측정, 잎 큐에넣고
잎제거하면서 차태워보냄
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.