Huomaa, että kaikki tiet ovat kaksisuuntaisia eli ei ole väliä, kummin päin kaupungit annetaan.
Voit olettaa, että kaupunkeja on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa. Jokaisen tien pituus on kokonaisluku välillä $1 \dots 1000$.
Toteuta tiedostoon
bestroute.py
luokka BestRoute
, jossa on seuraavat metodit:- konstruktori, jolle annetaan kaupunkien määrä
-
add_road
lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
-
find_route
ilmoittaa lyhimmän reitin pituuden kaupunkien $a$ ja $b$ välillä (tai $-1$, jos mitään reittiä ei ole)
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