Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
В первой строке входного файла INPUT.TXT записано единственное число N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. Элементы матрицы - целые числа от -1 до 100. На главной диагонали матрицы - всегда нули. Гарантируется, что в графе есть хотя бы одно ребро.
В выходной файл OUTPUT.TXT требуется вывести искомое максимальное кратчайшее расстояние.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
| 16 |
