Məsələlər
Флойд
Флойд
Дан ориентированный взвешенный граф. Найдите пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Giriş verilənləri
В первой строке содержится количество вершин графа n~(1 \le n \le 100). В следующих n строках находится по n чисел, которые задают весовую матрицу графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.
Çıxış verilənləri
Выведите искомое максимальное кратчайшее расстояние.
Nümunə
Giriş verilənləri #1
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0
Çıxış verilənləri #1
16