CSES - Lyhennys

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.

Toisin sanoen tehtävänä on selvittää, onko verkossa kahta solmua aa ja bb niin, että jos on olemassa mikä tahansa polku solmusta aa solmuun bb, voidaan löytää aina toinen polku, joka on vielä lyhempi.

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

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

  • konstruktori, jolle annetaan solmujen määrä
  • add_edge lisää solmusta aa solmuun bb kaaren, jonka paino on xx
  • check palauttaa True, jos solmusta aa solmuun bb 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