Задачі
Руйнування доріг
Руйнування доріг
Між кожною парою міст країни є пряма двостороння дорога. Петро хоче підірвати таку кількість доріг, щоб утворилося хоча б два міста, проїзд між якими був би неможливий.
Вам відома вартість підриву кожної дороги. Знайти найменшу вартість, за яку Петру вдасться здійснити задумане.
Вхідні дані
Складається з декількох тестів. Перший рядок кожного тесту містить кількість n (n ≤ 50) міст у країні. Наступні n рядків описують дороги: j-ий символ i-го рядка є цифрою, яка задає вартість знищення дороги, що веде з i-го міста в j-ий.
Вихідні дані
Для кожного тесту вивести в окремому рядку найменшу вартість, за яку Петру вдасться здійснити задумане.
Вхідні дані #1
4 0911 9011 1109 1190 6 030900 304120 040174 911021 027207 004170 4 0399 3033 9309 9390
Вихідні дані #1
4 8 9