In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
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.
Bajtockie Koleje Państwowe (BKP) stanęły przed koniecznością restrukturyzacji i redukcji sieci linii kolejowych. Po dokładnym przeanalizowaniu sieci linii kolejowych zdecydowano, które stacje kolejowe mają być zlikwidowane, a które mają pozostać. Zdecydowano się także maksymalnie zredukować sieć linii kolejowych. Trzeba jeszcze wybrać, które linie kolejowe mają być zlikwidowane, a które mają pozostać.
Sieć linii kolejowych składa się z odcinków torów łączących stacje kolejowe. Wiadomo, że z każdej stacji kolejowej da się dojechać do każdej innej stacji kolejowej (potencjalnie odwiedzając stacje pośrednie). Odcinki torów są dwukierunkowe. Między każdą parą stacji może być co najwyżej jeden odcinek torów. Każdy taki odcinek torów charakteryzuje się kosztem utrzymania, dodatnią liczbą całkowitą. Odcinki torów, które mają pozostać, muszą być tak wybrane aby:
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisane są dwie
dodatnie liczby całkowite i
,
,
(
),
oddzielone pojedynczym odstępem.
Liczba
to liczba stacji kolejowych, a
- liczba
odcinków torów.
Stacje kolejowe są ponumerowane od
do
.
W kolejnych
wierszach są opisane odcinki torów kolejowych,
po jednym w wierszu.
W każdym z tych wierszy są zapisane po trzy dodatnie liczby całkowite
,
i
,
,
,
.
Liczby
i
to numery stacji, które łączy dany odcinek torów,
a
to jego koszt utrzymania.
W
wierszu zapisany jest ciąg liczb całkowitych pooddzielanych
pojedynczymi odstępami.
Pierwsza z nich to
- liczba stacji, które mają pozostać (
,
).
Dalej w tym wierszu wymienione są numery tych stacji w kolejności
rosnącej.
W pierwszym wierszu standardowego wyjścia program powinien wypisać dwie
liczby całkowite i
oddzielone spacją, gdzie
jest sumarycznym
kosztem utrzymania pozostawionych odcinków, a
- liczbą tych odcinków.
W każdym z kolejnych
wierszy powinny znaleźć się dwie liczby
oraz
, oddzielone spacją - numery stacji, które łączą pozostawione odcinki
torów. Sumaryczny koszt utrzymania odcinków torów może być co najwyżej
dwukrotnie większy od najmniejszego kosztu, możliwego do uzyskania.
Dla danych wejściowych:
8 11 1 2 6 3 1 5 2 3 8 3 4 9 3 5 10 5 4 3 5 6 9 6 4 8 6 8 8 6 7 7 8 7 10 4 2 5 7 8
poprawną odpowiedzią jest:
42 5 2 3 3 5 5 6 6 7 6 8
Autor zadania: Marcin Kubica.