Distances

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 computing a distance table.

A distance table is an n \times n table where the entry on a row a and a column b is the length on the shortest route between the cities a and b. If there is no route, the entry is −1.

Here too all the roads go both directions and thus the order of the two cities makes no difference. There may be multiple roads between two cities.

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 allroutes.py, implement a class AllRoutes 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
• get_table returns the distance table as a two dimensional list

class AllRoutes:
    def __init__(self,n):
        # TODO

    def add_road(self,a,b,x):
        # TODO

    def get_table(self):
        # TODO

if __name__ == "__main__":
    a = AllRoutes(4)
    a.add_road(1,2,2)
    a.add_road(1,3,5)
    a.add_road(2,3,1)
    print(a.get_table())
    # [[0,2,3,-1],[2,0,1,-1],[3,1,0,-1],[-1,-1,-1,0]]