Paras reitti

Bittimaassa on $n$ kaupunkia, jotka on numeroitu $1,2,\dots,n$. Tiedossasi on kaupunkien väliset tiet, ja tehtäväsi on etsiä lyhimmän reitin pituus kaupungista toiseen.

Toteuta tiedostoon bestroute.py luokka BestRoute, jossa on seuraavat metodit:

• add_road: lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
• find_route: palauttaa lyhimmän reitin pituuden kaupungista $a$ kaupunkiin $b$

Kaikki tiet ovat kaksisuuntaisia, minkä takia ei ole merkitystä sillä, kummin päin kaupungit annetaan metodissa add_road. Voit olettaa, että kahden kaupungin välillä on enintään yksi tie.

Jos mitään reittiä ei ole olemassa, metodin find_route tulee palauttaa $-1$.

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__":
    routes = BestRoute(3)

    routes.add_road(1, 2, 2)
    print(routes.find_route(1, 3)) # -1

    routes.add_road(3, 1, 5)
    print(routes.find_route(1, 3)) # 5

    routes.add_road(2, 3, 1)
    print(routes.find_route(1, 3)) # 3