Sponsored
Sponsored
Using Depth-First Search (DFS), we can traverse the tree from the capital city '0' and calculate the minimum fuel cost required to gather all representatives in the capital city. We need to propagate the number of representatives from child nodes towards the root (capital) while managing the representatives getting into available seats effectively.
Time Complexity: O(n), where n is the number of cities as we visit each edge once.
Space Complexity: O(n), due to the storage used for the adjacency list and recursion stack.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<vector<int>> adjList;
6vector<bool> visited;
7
8int dfs(int node, int seats, long long &cost) {
9 visited[node] = true;
10 int representatives = 1;
11 for (const int &neighbor : adjList[node]) {
12 if (!visited[neighbor]) {
13 int rep_count = dfs(neighbor, seats, cost);
14 cost += (rep_count + seats - 1) / seats;
15 representatives += rep_count;
16 }
17 }
18 return representatives;
19}
20
21long long minimumFuelCost(vector<vector<int>> &roads, int seats) {
22 int n = roads.size() + 1;
23 adjList = vector<vector<int>>(n);
24 visited = vector<bool>(n, false);
25 for (auto &road : roads) {
26 adjList[road[0]].push_back(road[1]);
27 adjList[road[1]].push_back(road[0]);
28 }
29 long long cost = 0;
30 dfs(0, seats, cost);
31 return cost;
32}
33
34int main() {
35 vector<vector<int>> roads = {{3,1},{3,2},{1,0},{0,4},{0,5},{4,6}};
36 int seats = 2;
37 cout << minimumFuelCost(roads, seats) << endl;
38 return 0;
39}This C++ solution constructs an adjacency list to represent the tree structure of cities and computes the minimum fuel cost using depth-first search. It calculates costs based on representatives traveling to the capital city, managed effectively by the available seats per vehicle.
By utilizing Breadth-First Search (BFS), we can tackle this problem iteratively, processing nodes level by level from the capital outward. Track the representatives as they move towards the capital and the fuel cost incrementally.
Time Complexity: O(n) based on visiting each node.
Space Complexity: O(n) for queue storage.
1
This solution leverages BFS to maintain a queue for each city node. As nodes are processed, we calculate potential representatives from each node while incrementally updating fuel usage based on available seats. The BFS continues until all cities are visited.