Wschód-Zachód
Limit pamięci: 64 MB
Umowy międzynarodowe podpisane przez Wielce Rozległe Państwo
nakładają na nie obowiązek tranzytowy - musi ono umożliwić
przewiezienie koleją odpadów nuklearnych z elektrowni u
wschodniego sąsiada do punktów utylizacji za zachodnią
granicą.
Względy ekologiczne nakazują taką organizację ruchu,
by pociągi z odpadami jak najszybciej opuściły terytorium kraju.
Sieć kolejowa w tym państwie ma bardzo szczególną strukturę.
Składa się ona z miast-węzłów kolejowych oraz dwukierunkowych
odcinków torów, łączących miasta-węzły.
Między każdymi dwoma miastami istnieje możliwość przejazdu.
Ponadto istnieje
taki odcinek sieci, którego końce nie są miastami granicznymi,
oraz każdy przejazd z miasta na granicy wschodniej do miasta na
granicy zachodniej prowadzi przez ten odcinek.
Wszystkie pociągi z odpadami przyjeżdżają na granicę wschodnią
tego samego dnia
przed świtem, przy czym każdy z nich do innego miasta.
Ze względu na niebezpieczeństwo wypadku
pociągi jeżdżą tylko w dzień i po żadnym odcinku nie może
jednocześnie jechać więcej niż jeden pociąg z odpadami,
natomiast dowolnie
wiele takich pociągów może oczekiwać w mieście-węźle.
Dodatkowo przejechanie jednego odcinka zajmuje pociągowi jeden dzień.
Ruch
musi być tak zorganizowany, by każdy pociąg z odpadami
dojechał do innego przejścia na granicy zachodniej.
Ile co najmniej dni pociągi z odpadami muszą spędzić na
terytorium Wielce Rozległego Państwa?
Zadanie
Zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia opis sieci kolejowej i
przejść granicznych, do których przyjechały pociągi z
odpadami,
-
wyznaczy minimalną liczbę dni, jakie musi trwać
tranzyt,
-
wypisze znalezioną liczbę na standardowe wyjście.
Wejście
Pierwsza linia wejścia zawiera trzy pooddzielane
pojedyńczymi odstępami liczby naturalne
, .
Liczba oznacza liczbę miast-węzłów (są one
ponumerowane od 1 do ), zaś i oznaczają liczby
przejść granicznych odpowiednio na granicy wschodniej i
zachodniej. Przejścia na granicy wschodniej oznaczone są
liczbami , zaś na zachodniej liczbami
.
W kolejnych liniach znajduje się opis odcinków sieci
kolejowej. Każda linia opisu zawiera dwie różne liczby naturalne
oddzielone pojedynczym odstępem, .
Są to numery
miast-węzłów połączonych odcinkiem torów.
W -ej linii znajduje się jedna liczba naturalna , , oznaczająca liczbę pociągów z
odpadami.
W następnej (i ostatniej) linii wejścia znajduje się
pooddzielanych pojedyńczymi odstępami różnych liczb naturalnych,
z których
każda jest nie większa niż . Są to numery przejść
granicznych na granicy wschodniej,
do których przyjechały pociągi z odpadami.
Wyjście
Pierwsza i jedyna linia wyjścia powinna zawierać
dokładnie jedną liczbę całkowitą, równą minimalnej liczbie
dni, jakie odpady muszą spędzić na terytorium państwa.
Przykład
Dla danych wejściowych:
9 2 3
1 3
2 3
4 3
4 5
4 6
7 4
5 8
9 6
2
1 2
poprawną odpowiedzią jest:
4
Strzałki przedstawiają ruch pociągów w kolejnych dniach
dla jedej z optymalnych organizacji ruchu kolejowego - pętla
oznacza, że danego dnia pociąg stał w mieście-węźle.
Autor zadania: Karol Cwalina.