Задачи
Кратчайший путь
Кратчайший путь
Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.
Входные данные
Первая строка содержит натуральные числа n и m (n ≤ 2000, m ≤ 50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (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