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?

Voit olettaa, että kaupunkeja on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa. Jokaisen tien pituus on kokonaisluku välillä $1 \dots 1000$.

Python

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

• konstruktori, jolle annetaan kaupunkien määrä
• 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)

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

Java

Toteuta tiedostoon NewRoads.java luokka NewRoads, jossa on seuraavat metodit:

• konstruktori, jolle annetaan kaupunkien määrä
• addRoad tarjoaa kaupunkien $a$ ja $b$ välille tietä, jonka hinta on $x$
• minCost ilmoittaa pienimmän rakentamisen kokonaiskustannuksen (tai $-1$, jos ei ole mahdollista yhdistää kaikkia kaupunkeja)

public class NewRoads {
    public NewRoads(int n) {
        // TODO
    }

    public void addRoad(int a, int b, int x) {
        // TODO
    }

    public int minCost() {
        // TODO
    }

    public static void main(String[] args) {
        NewRoads n = new NewRoads(4);
        n.addRoad(1,2,2);
        n.addRoad(1,3,5);
        System.out.println(n.minCost()); // -1
        n.addRoad(3,4,4);
        System.out.println(n.minCost()); // 11
        n.addRoad(2,3,1);
        System.out.println(n.minCost()); // 7
    }
}