Змагання
Dijkstra algorithm
Відстань між вершинами
Задано неорієнтовний зважений граф. Знайти вагу мінімального шляху між двома вершинами.
Вхідні дані
Перший рядок містить натуральні числа n, m, s і f (n ≤ 5000, m ≤ 100000, 1 ≤ s, f ≤ n, s ≠ f`) - кількість вершин та ребер графа а також номери вершин, довжину шляху між якими потрібно знайти.
Наступні m рядків містять по три натуральних числа bi
, ei
і wi
- номери кінців i-го ребра та його вагу відповідно (1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100000).
Вихідні дані
У першому рядку вивести вагу мінімального шляху між вершинами s та f. У другому рядку через пропуск виведіть вершини на найкоротшому шдяху з s у f у порядку обходу. Якщо шлях з s у f не існує, виведіть -1.
Вхідні дані #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Вихідні дані #1
3 1 2 3