Uudet tiet

Bittimaassa on n kaupunkia, joiden välillä ei ole alussa teitä. Tavoitteena on yhdistää kaikki kaupungit toisiinsa teiden avulla.

Annettuna on joukko mahdollisia teitä ja jokaisesta tiestä rakentamisen hinta. Mikä on pienin kustannus, jolla voidaan rakentaa tieverkosto niin, että jokaisen kahden kaupungin välillä on reitti?

Toteuta tiedostoon newroads.py luokka NewRoads, jossa on seuraavat metodit:

• add_road tarjoaa kaupunkien a ja b välille tietä, jonka hinta on x
• min_cost ilmoittaa pienimmän rakentamisen kokonaiskustannuksen

Jos teiden avulla ei ole mahdollista yhdistää kaikkia kaupunkeja, metodin min_cost tulee palauttaa -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