Mudstock Bis
Limit pamięci: 32 MB
Władze zrzeszenia Holypolygons z okazji dziesiątej rocznicy pamiętnego
pierwszego zlotu swoich członków na błoniach w Mudstock, postanowiły
zorganizować wielki festiwal Mudstock bis.
Członkowie zrzeszenia mieszkają w wielu małych osadach Holypolylandii
położonych wzdłuż linii kolejowych (gdzie )
ponumerowanych kolejnymi liczbami naturalnymi od do .
Długość żadnej linii nie przekracza 500 km. Wszystkie linie mają początek w
stolicy i biegną promieniście od stolicy ku obrzeżom kraju. Linie te nie
krzyżują się. Każda osada nie będąca stolicą leży na dokładnie jednej linii. Na
każdej linii liczba osad jest dodatnia i nie większa niż 100. Liczba członków
zrzeszenia w jednej miejscowości również nie przekracza 100.
Każdą osadę, która nie jest stolicą identyfikujemy w jednoznaczny sposób za
pomocą dwóch współrzędnych , gdzie to numer
linii, na której leży osada, a to numer osady na linii. Osady na
każdej z linii numerujemy kolejno od stolicy. Przyjmujemy, że stolica (która
jest początkiem każdej linii) ma współrzędne .
Władze zrzeszenia fundują każdemu członkowi bilet kolejowy na powrót z
festiwalu do miejsca zamieszkania. Cena biletu jest równa liczbie przejechanych
kilometrów. Powstał więc problem, gdzie zorganizować festiwal, aby łączny koszt
przejazdu koleją wszystkich członków zrzeszenia z festiwalu do domu był
minimalny.
Zadanie
Ułóż program, który:
- wczytuje ze standardowego wejścia dane o sieci kolejowej: liczbę linii
kolejowych, liczbę członków zrzeszenia mieszkających w stolicy oraz dla każdej
osady liczbę mieszkających w niej członków stowarzyszenia i długość odcinka
linii kolejowej od tej osady do najbliższej stacji w kierunku stolicy;
- znajduje miejscowość, w jakiej należy zorganizować festiwal, aby łączny
koszt przejazdu koleją wszystkich jego uczestników (członków zrzeszenia) z
festiwalu do domu był minimalny,
- oblicza ten minimalny łączny koszt przejazdów;
- zapisuje wyniki w standardowym wyjściu
Jeżeli dla wielu miejscowości łączny koszt przejazdu koleją wszystkich członków
stowarzyszenia z danej miejscowości do domu jest minimalny, to Twój program
powinien znajdować jedną z nich.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite: liczba linii kolejowych ()
oraz liczba członków zrzeszenia mieszkających w stolicy kraju
().
W kolejnych wierszach znajdują się opisy linii o kolejnych
numerach od do . Każdy opis ma postać ciągu liczb
całkowitych pooddzielanych pojedynczymi odstępami.
Najpierw jest podana dodatnia liczba miejscowości, które leżą na danej linii
(nie licząc stolicy). Każda kolejna para liczb to: dodatnia odległość kolejnej
osady na danej linii od najbliższej osady w kierunku stolicy oraz nieujemna
liczba członków zrzeszenia mieszkających w tej osadzie. Bezpośrednio po
ostatniej liczbie każdego opisu następuje koniec wiersza.
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego
sprawdzać.
Wyjście
W pierwszym wierszu standardowego wyjścia należy zapisać minimalny łączny koszt
przejazdu koleją wszystkich członków stowarzyszenia z festiwalu do miejsca
zamieszkania, a w drugim wierszu współrzędne osady, w której należy
zorganizować festiwal.
Przykład
Dla danych wejściowych:
3 12
2 2 3 2 3
3 3 2 2 0 2 3
3 3 4 1 3 2 3
poprawną odpowiedzią jest:
87
0 0
Poniższy rysunek jest ilustracją testu przykładowego.
Autor zadania: Andrzej Walat.