|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 08-1. Форд-Беллман
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 100) - количество
вершин графа, далее идет число M (0 <= M <= 10000) - количество ребер.
Далее идет M троек чисел, описывающих ребра: начало ребра, конец ребра
и вес (вес - целое число от -100 до 100).
Формат выходных данных
В выходной файл выведите N чисел - расстояния от вершины номер 1 до
всех вешин графа. Если пути до соответствующей вершины не существует,
вместо длины пути выведите число 30000.
Пример
| input.txt | output.txt |
4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1 |
0 10 11 30000 |