CSES - New roads

Bitland has nn 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 xx between cities aa and bb
  • min_cost returns the smallest cost of connecting all cities

If it is not possible to connect all cities, the method min_cost should return 1-1.

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