Best route

Bitland has n cities that initially have no connecting roads. Your task is to design a class that supports adding a road between two cities and finding the shortest route between two cities.

All the roads go both directions and thus the order of the two cities makes no difference.

You may assume that the number of cities is at most 50 and that the methods of the class are called at most 100 times. The length of each road is an integer in the range 1 \dots 1000.

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

• constructor with the number of cities as a parameter
• add_road adds a road of length x between the cities a and b
• find_route returns the length of the shortest route between two cities a and b (or −1 if there is no route)

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