На часах 23:10. Только что закончилась очередная тренировка спортивных
программистов Bil-176. Измождённые и грустные студенты
медленно выползают из-за компьютеров. Одно согревает их: добрый тренер
Айбек агай готов развезти студентов по домам на своём
новеньком автомобиле. Хорошо, что пробок на дорогах нет. Плохо, что все
студенты живут в разных частях города. Айбек агай,
будучи программистом, выделил и пронумеровал пять ключевых точек на карте
Бишкека: место тренировки (1), дом Кутмана (2),
дом Олжобая (3), дома Элдара и Меерим (4; они живут рядом) и свой дом
(5). Теперь нужно составить оптимальный маршрут:
он должен начинаться в точке 1, заканчиваться в точке 5 и быть минимальным
по суммарному пройденному расстоянию. Более того,
Олжобай не согласен быть последним, кого отвезут домой, поэтому точка 3 не
может быть предпоследней в этом маршруте.
Исходные данные
На вход дана таблица расстояний между ключевыми точками. Она состоит из
пяти строк и пяти столбцов. j-е число в i-й строке
(1 ≤ i, j ≤ 5) —
это расстояние между точками i и j.
Все расстояния заданы в метрах и являются неотрицательными целыми
числами, не превосходящими 10 000. Гарантируется, что расстояние от любой
точки до самой себя равно нулю, и для любых двух точек расстояния туда и
обратно совпадают. Также гарантируется, что длина прямого пути между любыми двумя
точками не больше, чем длина любого пути между ними, проходящего через
другую точку.
Результат
Необходимо вывести одну строку. Сперва
суммарное пройденное расстояние в оптимальном маршруте.
Далее должны следовать пять чисел,
разделённых пробелом, — номера точек в порядке их посещения.
Если задача имеет несколько оптимальных решений, можно вывести любое из них.
Пример
| исходные данные | результат |
|---|
0 2600 3800 2600 2500
2600 0 5300 3900 4400
3800 5300 0 1900 4500
2600 3900 1900 0 3700
2500 4400 4500 3700 0
| 13500 1 2 3 4 5
|