CSES - Best route

Bitland has nn cities numbered 1,2,,n1,2,\dots,n. You know the roads between the cities, and your task is to find the shortest route between two cities.

In a file bestroute.py, implement the class BestRoute with the following methods:

  • add_road adds a road of length xx between the cities aa and bb
  • find_route returns the length of the shortest route between two cities aa and bb

All the roads go both directions and thus the order of the two cities in the method add_road makes no difference. You may assume that there is at most one road between any two cities.

If there is no route, the method find_route should return 1-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