|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
20.03.2019, 18:52 | #1 |
Новичок
Джуниор
Регистрация: 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 надеюсь, код будет не с миллионом всяких крутых процедур и тд, чтобы было понятно. Нужно к завтрашнему утру спасибо! |
20.03.2019, 19:03 | #2 |
Пользователь
Регистрация: 04.07.2012
Сообщений: 32
|
пишите, почта в подписи
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин | Daniia | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 19.03.2019 19:27 |
Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей] | barselona346736364 | Помощь студентам | 0 | 01.05.2013 16:35 |
Определение кратчайших путей по матричному методу. | bagfinder | Помощь студентам | 0 | 22.12.2011 13:30 |