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