e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Найкоротший шлях

Задано неорієнтиовний зважений граф. Знайти найкоротший шлях між двома заданими вершинами.

Вхідні умови

Перший рядок містить натуральні числа n та m (n2000, m50000) - кількість вершин та ребер графа. Другий рядок містить натуральні числа s та f (1s, fn, sf) - номери вершин, довжину шляху між якими потріно знайти. Наступні m рядків містять по три числа bi, ei та wi - номери кінців i-ого ребра та його вагу відповідно (1bi, ein, 0wi100000).

Вихідні умови

У першому рядку вивести довжину мінімального шляху між вершинами s та f. У другому рядку через пропуск виведіть вершини на найкоротшому шляху з s до f у порядку обходу. Якщо шляху з s до f не існує, виведіть -1.

prb4856.gif

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Вихідні дані #1
3
1 2 3