Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.03.2019, 19:27   #1
Daniia
Новичок
Джуниор
 
Регистрация: 19.03.2019
Сообщений: 3
По умолчанию посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

Входные данные
В первой строке входного файла записаны целые числа N и M - количество вершин и количество ребер графа (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В каждой из последующих M строк записана тройка чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

Выходные данные
В выходной файл выведите N чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.


Пример:

Вход: 4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1

Выход: 0 10 11 30000


спасибо!
Daniia вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
алгоритм Флойда поиска кратчайших путей в ориентированном графе на паскале Флауер Помощь студентам 5 06.06.2014 01:07
Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей] barselona346736364 Помощь студентам 0 01.05.2013 16:35
по трём координатам вершин прямоугольника найти координаты четвёртой вершины (Delphi) MaDDi Помощь студентам 7 14.02.2012 22:11
Определение кратчайших путей по матричному методу. bagfinder Помощь студентам 0 22.12.2011 13:30