Задачі
Флойд
Флойд
Задано орієнтований зважений граф. Знайдіть пару вершин, найкоротша відстань від однієї з яких до іншої максимальна серед усіх пар вершин.
\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