Задачи
Флойд
Флойд
Дан ориентированный взвешенный граф. Найдите пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
\InputFile
В первой строке содержится количество вершин графа $n~(1 \le n \le 100)$. В следующих $n$ строках находится по $n$ чисел, которые задают весовую матрицу графа. В ней $-1$ означает отсутствие ребра между вершинами, а любое неотрицательное число --- присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.
\OutputFile
Выведите искомое максимальное кратчайшее расстояние.
\includegraphics{https://eolympusercontent.com/images/9f3o95tvb17md528j8hbmbdqlk.gif}
Входные данные #1
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0
Выходные данные #1
16