Verkossa on n tietokonetta, joiden välillä ei ole vielä yhteyksiä. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään yhteyden kahden koneen välille sekä etsimään suorimman reitin kahden koneen välillä.

Voit olettaa, että tietokoneita on enintään 50 ja luokan metodeita kutsutaan enintään 100 kertaa.

Python

Toteuta tiedostoon network.py luokka Network, jossa on seuraavat metodit:

• konstruktori, jolle annetaan tietokoneiden määrä
• add_link lisää yhteyden kahden koneen välille
• best_route palauttaa pienimmän yhteyksien määrän reitillä kahden koneen välillä (tai -1 jos reittiä ei ole)

class Network:
    def __init__(self,n):
        # TODO

    def add_link(self,a,b):
        # TODO

    def best_route(self,a,b):
        # TODO

if __name__ == "__main__":
    w = Network(5)
    w.add_link(1,2)
    w.add_link(2,3)
    w.add_link(1,3)
    w.add_link(4,5)
    print(w.best_route(1,5)) # -1
    w.add_link(3,5)
    print(w.best_route(1,5)) # 2

Java

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

• konstruktori, jolle annetaan tietokoneiden määrä
• addLink lisää yhteyden kahden koneen välille
• bestRoute palauttaa pienimmän yhteyksien määrän reitillä kahden koneen välillä (tai -1 jos reittiä ei ole)

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

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

    public int bestRoute(int a, int b) {
        // TODO
    }

    public static void main(String[] args) {
        Network w = new Network(5);
        w.addLink(1,2);
        w.addLink(2,3);
        w.addLink(1,3);
        w.addLink(4,5);
        System.out.println(w.bestRoute(1,5)); // -1
        w.addLink(3,5);
        System.out.println(w.bestRoute(1,5)); // 2
    }
}