Задачі
Алгоритм Йена
Алгоритм Йена
Знайдіть 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