Самый длинный путь
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Дан ориентированный взвешенный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины).
Требуется найти две вершины, кратчайший путь между которыми имеет наибольшую длину.
Входные данные
В первой строке входного файла INPUT.TXT задано число вершин N (3 ≤ N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 106. Гарантируется, что на главной диагонали матрицы стоят нули.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – длину искомого пути.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3
0 7 3
7 0 10
2 215 0 | 10 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|