Toisin sanoen tehtävänä on selvittää, onko verkossa kahta solmua $a$ ja $b$ niin, että jos on olemassa mikä tahansa polku solmusta $a$ solmuun $b$, voidaan löytää aina toinen polku, joka on vielä lyhempi.
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$.
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
palauttaaTrue
, jos solmusta $a$ solmuun $b$ on äärettömän lyhyt polku, ja muutenFalse
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