eolymp
bolt
Try our new interface for solving problems
Məsələlər

Флойд

Флойд

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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