Suunnattu painotettu verkko on aluksi tyhjä. Tehtäväsi on toteuttaa luokka, jonka avulla voi lisätä kaaria verkkoon sekä tarkastaa, onko verkossa äärettömän lyhyttä polkua tietystä solmusta toiseen.

Voit olettaa, että solmuja on enintään $50$, luokan metodeita kutsutaan enintään $100$ kertaa ja jokaisen kaaren paino on välillä $-1000 \dots 1000$.

Python

Toteuta tiedostoon shortening.py luokka Shortening, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
• add_edge lisää solmusta $a$ solmuun $b$ kaaren, jonka paino on $x$
• check palauttaa True, jos solmusta $a$ solmuun $b$ on äärettömän lyhyt polku, ja muuten False

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

    def add_edge(self,a,b,x):
        # TODO

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

if __name__ == "__main__":
    s = Shortening(5)
    print(s.check(1,3)) # False
    s.add_edge(1,2,5)
    s.add_edge(2,3,-2)
    print(s.check(1,3)) # False
    s.add_edge(2,4,1)
    s.add_edge(4,2,-2)
    print(s.check(1,3)) # True

Java

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

• konstruktori, jolle annetaan solmujen määrä
• addEdge lisää solmusta $a$ solmuun $b$ kaaren, jonka paino on $x$
• check palauttaa True, jos solmusta $a$ solmuun $b$ on äärettömän lyhyt polku, ja muuten False

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

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

    public boolean check(int a, int b) {
        // TODO
    }

    public static void main(String[] args) {
        Shortening s = new Shortening(5);
        System.out.println(s.check(1,3)); // false
        s.addEdge(1,2,5);
        s.addEdge(2,3,-2);
        System.out.println(s.check(1,3)); // false
        s.addEdge(2,4,1);
        s.addEdge(4,2,-2);
        System.out.println(s.check(1,3)); // true
    }
}