e-olymp
Задачи

Флойд

Флойд

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

Входные данные

В первой строке содержится количество вершин графа n (1n100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
Выходные данные #1
16