W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mała myszka została zamknięta w wielkim labiryncie.
Labirynt ten składa się z pokoi, między którymi jest korytarzy. Jednak każdy korytarz ma jakąś szerokość i jeżeli myszka będzie zbyt gruba, to nie będzie w stanie się przez niego przecisnąć.
Zadania nie ułatwia morzący ją głód. W niektórych pokojach znajduje się kawałek przepysznego sera. Jeżeli myszka kiedykolwiek wejdzie do tego pokoju, to nie może się oprzeć i zjada cały kawałek. Zjedzenie kawałka sera może sprawić, że myszce przybędzie na masie i może jej to uniemożliwić korzystania z niektórych korytarzy.
Znając plan labiryntu, szerokość korytarzy, rozmieszczenie kawałków sera, początkowe położenie myszki oraz pokój, który jest wyjściem z labiryntu, odpowiedz na pytanie, jaka może być największa początkowa grubość myszki, tak aby było możliwe wyjście z labiryntu. Zakładamy, że początkowa waga myszki jest większa bądz równa 0.
W pierszym wierszu wejścia znajdują się cztery liczby całkowite (), oznaczające kolejno: liczbę pokoi w labiryncie, liczbę korytarzy, początkową pozycję myszki oraz numer pokoju w którym znajduje się wyjście z labiryntu.
W kolejnym wierszu znajduje się liczb całkowitych (), gdzie oznacza że grubość myszki się zwiększy o , jeżeli zje ona ser z -tego pokoju (jeżeli , to w tym pokoju nie ma sera).
W kolejnych wierszach znajduje się opis kolejnych korytarzy. Każdy korytarz opisany jest przez trzy liczby całkowite (), oznaczające, że dany korytarz łączy pokoje oraz i myszka może mieć grubość maksymalnie , aby przecisnąć się przez dany korytarz.
Wyjście powinno zawierać jedną liczbę całkowitą, równą maksymalnej wadze myszki, takiej że myszka jest w stanie wydostać się z labiryntu, lub -1, jeśli myszka nie może wydostać się z labiryntu.
Dla danych wejściowych:
2 1 1 2 1 0 1 2 5
poprawną odpowiedzią jest:
4
Autor zadania: Adrian Jaskółka.