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 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 (tai -1, jos ei ole mahdollista yhdistää kaikkia kaupunkeja)

Toteuta luokka tiedostoon newroads.py seuraavan esimerkin mukaisesti.

class NewRoads:
    def __init__(self, n):
        # TODO

    def add_road(self, a, b, x):
        # TODO

    def min_cost(self):
        # TODO

if __name__ == "__main__":
    n = NewRoads(4)
    n.add_road(1, 2, 2)
    n.add_road(1, 3, 5)
    print(n.min_cost()) # -1
    n.add_road(3, 4, 4)
    print(n.min_cost()) # 11
    n.add_road(2, 3, 1)
    print(n.min_cost()) # 7