Кратчайший путь
Задан ориентированный граф без кратных ребер. Найти кратчайший
путь между двумя вершинами. Все веса ребер положительны. Путь
всегда существует.
Ограничения
Максимальное количество вершин не больше 100.
Входные и выходные данные
Во входном файле в первой строке два числа -
n - количество вершин в графе, и m - число ребер в графе.
В следующей строке номера начальной и конечной вершины.
Далее, в m строчках записаны по три числа, описывающие
по одному ребру. Первое число - номер вершины, из которой
идет ребро, второе - номер вершины куда идет ребро,
третье число - вес ребра (от 0 до 1000). В выходной файл
необходимо выдать стоимость кратчайшего пути из начальной
вершины в конечную, и затем сам этот путь: номера вершин
через пробел, включая начальную и конечную вершину.
Пример входного файла
4 6
2 3
2 1 1
2 3 25
4 3 10
2 4 2
1 3 3
1 2 0
Пример выходного файла
4
2 1 3
|
