eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Авиаперелёты

Авиаперелёты

Лимит времени 4 секунды
Лимит использования памяти 128 MiB

Главного конструктора Петю попросили разработать новую модель самолета для компании "Air Бубундия". Оказалось, что самая сложная часть заключается в подборе оптимального размера топливного бака.

Главный картограф "Air Бубундия" Вася составил подробную карту Бубундии. На этой карте он отметил расход топлива для перелета между каждой парой городов.

Петя хочет сделать размер бака минимально возможным, для которого самолет сможет долететь от любого города в любой другой (возможно, с дозаправками в городах на пути следования).

Входные данные

Первая строка содержит количество городов в Бубундии n (1n1000). Далее идут n строк по n чисел каждая. j-ое число в i-ой строке равно расходу топлива при перелете из i-ого города в j-ый. Все числа не меньше нуля и меньше 10^9. Гарантируется, что для любого i в i-ой строке i-ое число равно нулю.

Выходные данные

Одно число - оптимальный размер бака.

1936.gif

Пример

Входные данные #1
4
0 10 12 16
11 0 8 9
10 13 0 22
13 10 17 0
Выходные данные #1
10
Автор Виталий Гольдштейн
Источник Зимняя школа, Харьков 2011, День 9