One post tagged with "Breadth-First Search"

In this problem, we are given a tree structure of a city plan. By that, it means that we have a graph of $n$ nodes that consists of exactly $n-1$ edges. The graph is also connected, i.e., it is possible to travel from one city to any other one. The setting is that the capital city is marked at node 0, and every other city has one representative that needs to come to the capital. They can travel together in a car, which has a limited number of seats. The problem asks us to find the minimum number of fuels used, considering that moving from one to another city takes exactly 1 liter of fuel.