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

Strong Connected Components

Авіаперельоти

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

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

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

Вхідні дані

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

Вихідні дані

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

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