|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.03.2019, 19:27 | #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 спасибо! |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
алгоритм Флойда поиска кратчайших путей в ориентированном графе на паскале | Флауер | Помощь студентам | 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 |