АВТ
Язык:

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

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

783. Флойд-макс

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

 
Задача "Флойд-Макс"

Дан ориентированный взвешенный граф. В нём вам необходимо найти пару 
вершин, кратчайшее расстояние от одной из которых до другой 
максимально среди всех пар вершин.

Входные данные:
В первой строке входного файла единственное число: N (1 <= N <= 100) - 
количество вершин графа. В следующих N строках по N чисел - 
матрица смежности графа (j-ое число в i-ой строке соответствует
ребру из вершины i в вершину j): -1 означает отсутствие ребра между 
вершинами, а любое неотрицательное число - присутствие 
ребра данного веса. На главной диагонали матрицы - всегда нули.

Выходные данные:
Вывести искомое максимальное кратчайшее расстояние.

Пример входного файла
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0

Пример выходного файла
16

Статистика Послать на проверку Обсуждение задачи Автор/источник: olympiads.ru
Учебные курсы / Задачи с olympiads.ru /
782. 258 - Флойд-1 783. 784. 260 - Флойд-существование 785. 261 - Путь-2 786. 262 - Форд-Беллман
 
время генерации 0.11 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.