Bitland has cities but initially no roads between them. The goal is to connect all cities to each other.
You are given a set of possible roads and the construction cost for each road. What is the smallest cost of a road network that connects all cities?
In a file newroads.py
, implement the class NewRoads
with the following methods:
add_road
adds a possible road of cost between cities andmin_cost
returns the smallest cost of connecting all cities
If it is not possible to connect all cities, the method min_cost
should return .
class NewRoads: def __init__(self, n): # TODO def add_road(self, a, b, x): # TODO def min_cost(self): # TODO if __name__ == "__main__": new_roads = NewRoads(4) new_roads.add_road(1, 2, 2) new_roads.add_road(1, 3, 5) print(new_roads.min_cost()) # -1 new_roads.add_road(3, 4, 4) print(new_roads.min_cost()) # 11 new_roads.add_road(2, 3, 1) print(new_roads.min_cost()) # 7