АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

785. Путь-2

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

 
Кратчайший путь

Задан ориентированный граф без кратных ребер. Найти кратчайший 
путь между двумя вершинами. Все веса ребер положительны. Путь 
всегда существует.

Ограничения
Максимальное количество вершин не больше 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


Статистика Послать на проверку Обсуждение задачи Автор/источник: olympiads.ru
Учебные курсы / Задачи с olympiads.ru /
784. 260 - Флойд-существование 785. 786. 262 - Форд-Беллман 787. 263 - Лабиринт знаний 788. 264 - Цикл
 
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.