Paras reitti

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ä.

Luokassa tulee olla seuraavat metodit:

• add_road: lisää tien kaupungista $a$ kaupunkiin $b$, jonka pituus on $x$
• find_route: palauttaa lyhimmän reitin pituuden kaupungista $a$ kaupunkiin $b$ (jos mitään reittiä ei ole olemassa, metodin tulee palauttaa $-1$)

Kaupungit on numeroitu $1,2,\dots,n$. Huomaa, että kaikki tiet ovat kaksisuuntaisia eli ei ole väliä, kummin päin kaupungit annetaan.

Toteuta tiedostoon bestroute.py luokka BestRoute, joka toimii seuraavan esimerkin mukaisesti.

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