Олимпиадный тренинг

Задача . Самый длинный путь


Задача

Темы: Алгоритм Флойда
Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.
 
Входные данные
В первой строке задано число вершин N ≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.
 
Выходные данные
Выведите одно число – длину искомого пути.

Примеры
Входные данные Выходные данные
1
3
0 7 3
7 0 10
2 215 0
10
 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6462
Python19
Комментарий учителя