D. Мистер Флойд

2000 мс · 256 МБ · всё или ничего

Дан ориентированный взвешенный граф матрицей смежности. Найдите пару вершин, кратчайшее расстояние между которыми максимально среди всех пар.

Формат ввода

Первая строка содержит число $n$ ( $1 \le n \le 100$ ).

Далее идут $n$ строк по $n$ чисел: $-1$ означает отсутствие ребра, неотрицательное число — вес. Вес не превосходит $10^4$ , на главной диагонали нули.

Формат вывода

Одно число — наибольшее конечное кратчайшее расстояние. Если пути нет ни между какой парой различных вершин, выведите $0$ .

Примеры

ввод

6
0 6 8 -1 -1 -1
5 0 5 -1 -1 -1
1 7 0 -1 -1 -1
-1 -1 -1 0 6 -1
-1 -1 -1 -1 0 3
-1 -1 -1 2 -1 0

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.