|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 07-2. Флойд
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Формат входных данных
В первой строке входного файла единственное число N (1 <= N <= 100) -
количество вершин графа. В следующих N строках по N чисел -
матрица смежности графа, где -1 означает отсутствие ребра между
вершинами, а любое неотрицательное число - присутствие
ребра данного веса. На главной диагонали матрицы - всегда нули.
Формат выходных данных
Вывести искомое максимальное кратчайшее расстояние.
Пример
| input.txt | output.txt |
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0 |
16 |