Задачи
Продавец аквариумов
Продавец аквариумов
Продавец аквариумов для кошек хочет объехать \textbf{n} городов, посетив каждый из них ровно один раз. Помогите ему найти кратчайший путь.
\includegraphics{https://static.e-olymp.com/content/58/58b188e43340b321cb1c5785092b9b9252d7b01f.jpg}
\InputFile
Первая строка входного файла содержит натуральное число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{13}) - количество городов. Следующие \textbf{n}строк содержат \textbf{n} чисел - длины путей между городами.
В \textbf{i}-ой строке \textbf{j}-ое число, \textbf{a_\{i,j\}} - это расстояние между городами \textbf{i} и \textbf{j} (\textbf{0} ≤ \textbf{a_\{i,j\}} ≤ \textbf{10^6}, \textbf{a_\{i,j\} = a_\{j,i\}}, \textbf{a_\{i,i\} = 0}).
\OutputFile
В первой строке выходного файла выведите длину кратчайшего пути. Во второй стороке выведите \textbf{n} чисел - порядок, в котором нужно посетить города.
Входные данные #1
5 0 183 163 173 181 183 0 165 172 171 163 165 0 189 302 173 172 189 0 167 181 171 302 167 0
Выходные данные #1
666 4 5 2 3 1