In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Sieć kolejowa Bajtockich Kolei Bitowych (BKB) składa się z dwukierunkowych odcinków torów łączących pewne pary stacji. Każda para stacji jest połączona co najwyżej jednym odcinkiem torów. Ponadto wiadomo, że z każdej stacji kolejowej można dojechać do każdej innej dokładnie jedną trasą. (Trasa może być złożona z kilku odcinków torów, ale nigdy nie przechodzi przez żadną stację więcej niż raz).
Bajtazar jest tajnym inspektorem BKB.
W celu przeprowadzenia inspekcji wybiera jedną ze stacji (oznaczmy ją ), w której organizuje sobie centralę,
i rozpoczyna podróż po wszystkich innych stacjach.
Podróż ma następujący przebieg:
Bajtazar pragnie rozważyć wszystkie możliwe stacje jako stacje początkowe .
Dla każdej z nich chcemy wyznaczyć kolejność, w jakiej Bajtazar powinien kontrolować pozostałe stacje,
tak aby łącznie jak najmniej czasu spędził na przejazdach, o ile dla danej stacji
w ogóle taka kolejność istnieje.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (
), oznaczającą liczbę stacji.
Stacje są ponumerowane od 1 do
.
Kolejne
wierszy opisuje odcinki torów, po jednym w wierszu.
W każdym z nich znajdują się dwie liczby całkowite
(
,
), oddzielone pojedynczym odstępem,
oznaczające, że istnieje odcinek torów łączący stacje
i
.
Każdy odcinek torów pojawia się w opisie dokładnie raz.
W testach wartych przynajmniej 30% punktów zachodzi dodatkowy warunek .
Twój program powinien wypisać na standardowe wyjście wierszy, a w każdym z nich po jednej liczbie całkowitej.
Liczba w
-tym wierszu powinna być równa minimalnej liczbie godzin, jakie Bajtazar musi spędzić na przejazdach,
aby skontrolować stacje, dla
- o ile dla
szukana kolejność stacji istnieje.
W przeciwnym przypadku, w
-tym wierszu powinna znaleźć się liczba
.
Dla danych wejściowych:
9 3 6 2 4 2 6 2 5 1 7 2 7 8 9 7 8
poprawną odpowiedzią jest:
-1 23 -1 -1 -1 -1 -1 -1 -1
Rysunek pokazuje przykładową sieć połączeń.
Szukana kolejność, w jakiej Bajtazar powinien kontrolować stacje, istnieje tylko dla .
Może to być na przykład:
,
,
,
,
,
,
,
.
Przy takiej kolejności kontrolowanych stacji Bajtazar spędzi na przejazdach łącznie
godziny.
Autorzy zadania: Wojciech Rytter i Bartosz Szreder.