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