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