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$.

Python

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

Java

Toteuta tiedostoon AllRoutes.java luokka AllRoutes, jossa on seuraavat metodit:

• konstruktori, jolle annetaan kaupunkien määrä
• addRoad lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
• getTable palauttaa välimatkataulukon kaksiulotteisena taulukkona

import java.util.*;

public class AllRoutes {
    public AllRoutes(int n) {
        // TODO
    }

    public void addRoad(int a, int b, int x) {
        // TODO
    }

    public int[][] getTable() {
        // TODO
    }

    public static void main(String[] args) {
        AllRoutes a = new AllRoutes(4);
        a.addRoad(1,2,2);
        a.addRoad(1,3,5);
        a.addRoad(2,3,1);
        System.out.println(Arrays.deepToString(a.getTable()));
        // [[0,2,3,-1],[2,0,1,-1],[3,1,0,-1],[-1,-1,-1,0]]
    }
}