diff options
Diffstat (limited to 'min_fuel_report_captial.cpp')
-rw-r--r-- | min_fuel_report_captial.cpp | 50 |
1 files changed, 0 insertions, 50 deletions
diff --git a/min_fuel_report_captial.cpp b/min_fuel_report_captial.cpp deleted file mode 100644 index 5d13beb..0000000 --- a/min_fuel_report_captial.cpp +++ /dev/null @@ -1,50 +0,0 @@ -// 2477. Minimum Fuel Cost to Report to the Capital -#include "leetcode.h" - -/* - * there is a tree (ie. a connected, undirected graph with no cycles) structure - * country network consisting of 'n' cities numbered from 0 to 'n - 1' and - * exactly 'n - 1' roads the capital city is city 0. given a 2d integer array - * 'roads' where 'roads[i] = [ai, bi]' denotes that there exists a bidirectional - * road connecting cities ai & bi. there is a meeting for the representitive of - * each city. the meeting is in the capital city. there is a car in each city. - * given integer seats that indicates the number of seats in each car. a - * representitive can use the car in their city to travel or change the car and - * ride with another representitive. the cost of traveling between two cities is - * 1 liter of fuel. return minimum number of liters of fuel needed to reach - * capital city. - */ - -class Solution { -public: - long long minimumFuelCost(vvd(int) & roads, int seats) { - vvd(int) al(roads.size() + 1); - for (auto &r : roads) { - al[r[0]].push_back(r[1]); - al[r[1]].push_back(r[0]); - } - long long ans = 0; - return dfs(0, -1, 0, seats, al, ans); - } - -private: - long long dfs(int i, int prev, int depth, int seats, vvd(int) & al, - long long &ans) { - long long riders = 1; - for (int j : al[i]) - if (j != prev) - riders += dfs(j, i, depth + 1, seats, al, ans); - if (depth == 0) - return ans; - ans += (riders / seats) * depth + (riders % seats ? 1 : 0); - return riders % seats; - } -}; - -int main() { - Solution obj; - vvd(int) roads1 = {{0, 1}, {0, 2}, {0, 3}}; - vvd(int) roads2 = {{3, 1}, {3, 2}, {1, 0}, {0, 4}, {0, 5}, {4, 6}}; - cout << obj.minimumFuelCost(roads1, 5) << endl; // expect: 3 - cout << obj.minimumFuelCost(roads2, 2) << endl; // expect: 7 -} |