In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.