Привіт, Пиріг!#1105
Піцерія Pizazz пишається тим, що доставляє піцу своїм клієнтам якнайшвидше. На жаль, для доставки можна найняти лише одного водія. Перед початком доставки водій чекає, доки не надійде певна кількість замовлень (від до ). Потім водій обирає найшвидший можливий маршрут, щоб доставити всі замовлення, навіть якщо для цього потрібно відвідати одну й ту саму локацію кілька разів, включаючи саму піцерію. Наприкінці маршруту доставки водій обов’язково повинен повернутися у початкове місце, тобто в піцерію. Вам потрібно написати програму, яка визначить мінімальний час такого маршруту.
Перший рядок містить одне ціле число (1 \le n \le 20) — кількість замовлень.
Далі йдуть n + 1 рядків, кожен з яких містить по n + 1 цілих чисел. Ці числа описують час переїзду між точками: піцерією (номер ) та локаціями із замовленнями (нумеруються від до ).
-те число в -му рядку означає час, необхідний для прямої поїздки з точки в точку без зупинок у інших точках по дорозі.
Зверніть увагу, що через затори й світлофори прямий час поїздки з у може бути не коротший, ніж з об’їздом через інші точки; часи проїзду не обов’язково симетричні, тобто час поїздки з в може відрізнятися від часу з в .
Виведіть одне ціле число — мінімальний загальний час, необхідний для доставки піци всім клієнтам і повернення у піцерію.
Приклад 1