Задача №112654. Путь почтальона - 3
Почтальон Печкин ежедневно разносит письма и газеты жителям Простоквашино. Деревня большая, люди живут на хуторах. Печкин хочет каждый день обязательно обойти все хутора, посетив каждый из них только по одному разу. Этот маршрут должен начинаться и заканчиваться на почте. В Простоквашино очень много дорог и тропинок, и Печкин хочет выбрать маршрут минимальной длины. Напишите программу, которая поможет Печкину выбрать наилучший (оптимальный) маршрут.
В первой строке вводится количество хуторов N ( 1 ≤ N ≤ 15 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему расположения хуторов. Положительное число в матрице означает расстояние между хуторами, а ноль говорит о том, что прямой дороги нет.
В первой строке программа должна вывести общую длину оптимального маршрута. Во второй строке выводится сам маршрут (последовательность номеров хуторов), который начинается с 1 и заканчивается на 1 (пункт номер 1 – это почта). Второй номер пункта в записи маршрута должен быть минимальный из возможных.
4 0 1 8 4 1 0 2 5 8 2 0 3 4 5 3 0
10 1 2 3 4 1