Задачи
Флойд
Флойд
Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Входные данные
В первой строке содержится количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел, которые задают весовую матрицу графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.
Выходные данные
Вывести искомое максимальное кратчайшее расстояние.
Пример
Входные данные #1
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0
Выходные данные #1
16