Задачи
Расстояние между вершинами
Расстояние между вершинами
Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.
Входные данные
Первая строка содержит натуральные числа n, m, s и f (n ≤ 5000, m ≤ 105
, 1 ≤ s, f ≤ n, s ≠ f) - количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.
Следующие m строк содержат по три натуральных числа bi
, ei
и wi
- номера концов i-ого ребра и его вес соответственно (1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 105
).
Выходные данные
Первая строка должна содержать вес минимального пути между вершинами 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