Välimatkat

Bittimaassa on $n$ kaupunkia, joiden välillä ei ole vielä teitä. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään tien kahden kaupungin välille sekä muodostamaan taulukon kaupunkien välimatkoista.

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]]