Välimatkataulukko on $n \times n$ kokoinen taulukko, jonka rivillä $a$ sarakkeessa $b$ lukee lyhin reitin pituus kaupunkien $a$ ja $b$ välillä. Jos mitään reittiä ei ole olemassa, reitin pituus on $-1$.
Tässäkin tehtävässä kaikki tiet ovat kaksisuuntaisia eli ei ole väliä, kummin päin kaupungit annetaan. Huomaa, että kahden kaupungin välillä voi olla useita teitä.
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
allroutes.py
luokka AllRoutes
, jossa on seuraavat metodit:- konstruktori, jolle annetaan kaupunkien määrä
-
add_road
lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
-
get_table
palauttaa välimatkataulukon kaksiulotteisena listana
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]]