leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2477.cpp (953B)

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 };