Bittimaassa on $n$ kaupunkia, joiden välillä ei ole vielä teitä. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään tien kahden kaupungin välille sekä etsimään lyhimmän reitin kahden kaupungin välillä.

Huomaa, että kaikki tiet ovat kaksisuuntaisia eli ei ole väliä, kummin päin kaupungit annetaan.

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 bestroute.py luokka BestRoute, jossa on seuraavat metodit:

• konstruktori, jolle annetaan kaupunkien määrä
• add_road lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
• find_route ilmoittaa lyhimmän reitin pituuden kaupunkien $a$ ja $b$ välillä (tai $-1$, jos mitään reittiä ei ole)

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

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

    def find_route(self,a,b):
        # TODO

if __name__ == "__main__":
    b = BestRoute(3)
    b.add_road(1,2,2)
    print(b.find_route(1,3)) # -1
    b.add_road(1,3,5)
    print(b.find_route(1,3)) # 5
    b.add_road(2,3,1)
    print(b.find_route(1,3)) # 3

Java

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

• konstruktori, jolle annetaan kaupunkien määrä
• addRoad lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
• findRoute ilmoittaa lyhimmän reitin pituuden kaupunkien $a$ ja $b$ välillä (tai $-1$, jos mitään reittiä ei ole)

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

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

    public int findRoute(int a, int b) {
        // TODO
    }

    public static void main(String[] args) {
        BestRoute b = new BestRoute(3);
        b.addRoad(1,2,2);
        System.out.println(b.findRoute(1,3)); // -1
        b.addRoad(1,3,5);
        System.out.println(b.findRoute(1,3)); // 5
        b.addRoad(2,3,1);
        System.out.println(b.findRoute(1,3)); // 3
    }
}