Та же задача, что и предыдущая, но 3<=N<=13
Ограничение времени работы на одном тесте - 10 секунд
Задача коммивояжера
Дан граф без петель и кратных ребер, все ребра имеют вес, выражающийся
натуральным числом. Требуется в этом графе найти путь, проходящий
по всем вершинам (причем по каждой - ровно один раз), и в конце
возвращающийся в начальную вершину, при этом суммарный вес всех
ребер в этом пути должен быть минимально возможным.
Входные данные
Во входном файле записано сначала число N (3<=N<=13). Затем идет
матрица смежности графа (N*N чисел), число в i-ой строке j-ом столбце
описывает ребро между вершинами i и j: если ребро существует,
то это число равно его весу, если ребра не существует, то записано
число 0.
Граф неориентированный, то есть матрица симметрична относительно главной
диагонали, на главной диагонали стоят нули.
Вес каждого ребра задается натуральным числом от 1 до 1000.
Выходные данные
В выходной файл выведите N+1 число - найденный путь (первая и последняя
его вершины должны совпадать). Гарантируется, что путь всегда
существует.
Пример входного файла
4
0 0 10 20
0 0 3 10
10 3 0 2
20 10 2 0
Пример выходного файла
1 3 2 4 1
|
