Bitland has cities numbered . 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 between the cities andfind_route
returns the length of the shortest route between two cities and
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 .
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