e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Strong Connected Components

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

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

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

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

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

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

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

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

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