eolymp
Задачі

Флойд

Флойд

Задано орієнтований зважений граф. Знайти пару вершин, найкоротша відстань від однієї з яких до іншої максимальна серед усіх пар вершин.

Вхідні дані

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

Вихідні дані

Вивести шукану максимальну найкоротшу відстань.

prb975.gif

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