@Антон Блик

На часах 23:10. Только что закончилась очередная тренировка спортивных программистов мат-меха. Измождённые и грустные студенты медленно выползают из-за компьютеров. Одно согревает их: добрый тренер дядя Миша готов развезти студентов по домам на своём новеньком автомобиле. Хорошо, что пробок на дорогах нет. Плохо, что все студенты живут в разных частях города. Дядя Миша, будучи программистом, выделил и пронумеровал пять ключевых точек на карте Екатеринбурга: место тренировки (1), дом Кирилла (2), дом Ильи (3), дома Паши и Олега (4; они живут рядом) и свой дом (5). Теперь нужно составить оптимальный маршрут: он должен начинаться в точке 1, заканчиваться в точке 5 и быть минимальным по суммарному пройденному расстоянию. Более того, Илья не согласен быть последним, кого отвезут домой, поэтому точка 3 не может быть предпоследней в этом маршруте.
Исходные данные
На вход дана таблица расстояний между ключевыми точками. Она состоит из пяти строк и пяти столбцов. j-е число в i-й строке (1 ≤ i, j ≤ 5) — это расстояние между точками i и j. Все расстояния заданы в метрах и являются неотрицательными целыми числами, не превосходящими 10 000. Гарантируется, что расстояние от любой точки до самой себя равно нулю, и для любых двух точек расстояния туда и обратно совпадают. Также гарантируется, что длина прямого пути между любыми двумя точками не больше, чем длина любого пути между ними, проходящего через другую точку.
Результат
Необходимо вывести две строки. Первая строка должна содержать суммарное пройденное расстояние в оптимальном маршруте. Вторая строка должна содержать пять чисел, разделённых пробелом, — номера точек в порядке их посещения. Если задача имеет несколько оптимальных решений, можно вывести любое из них.

0