Задача "Флойд-Макс"
Дан ориентированный взвешенный граф. В нём вам необходимо найти пару
вершин, кратчайшее расстояние от одной из которых до другой
максимально среди всех пар вершин.
Входные данные:
В первой строке входного файла единственное число: 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
|
