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.
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.