Задачи
Алгоритм Йена
Алгоритм Йена
Найдите k-ый кратчайший путь между двумя фиксированными вершинами в неориентированном графе.
Входные данные
В первой строке содержатся количество вершин n (1 ≤ n ≤ 100) и рёбер m (1 ≤ m ≤ 4000) в графе, а также порядковый номер пути k (1 ≤ k ≤ 500). В следующих строках описываются рёбра графа - тройка (u, v, w) описывает ребро, соединяющее вершины u и v весом w. В последней строке содержатся номера двух вершин s и t, между которыми требуется искать путь.
В графе не может быть кратных рёбер, не может быть петель. Все веса положительны и не превышают 10000. Гарантируется, что искомый путь существует.
Выходные данные
В первой строке выведите два числа - искомый вес пути и число вершин в нём. В следующей строке выведите сам путь - последовательность номеров вершин.
Пример
Входные данные #1
5 10 3 1 2 6 1 3 13 1 4 18 1 5 35 2 3 14 2 4 34 2 5 17 3 4 22 3 5 15 4 5 34 1 5
Выходные данные #1
35 2 1 5