|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Сложность Гамма
Задача коммивояжёра
English
Дан граф без петель и кратных рёбер, все рёбра имеют вес, выражающийся
натуральным числом. Требуется в этом графе найти путь, проходящий
по всем вершинам (причем по каждой - ровно один раз), и в конце
возвращающийся в начальную вершину, при этом суммарный вес всех
рёбер в этом пути должен быть минимально возможным.
Ввод
На входе записано сначала число N (3 ≤ N ≤ 9). Затем
идет матрица смежности графа (N*N чисел), число в i-ой
строке j-ом столбце описывает ребро между вершинами i и
j: если ребро существует, то это число равно его весу, если ребра
не существует, то записано число 0.
Граф неориентированный, то есть матрица симметрична относительно главной
диагонали, на главной диагонали стоят нули.
Вес каждого ребра задается натуральным числом от 1 до 1000.
Вывод
Выведите N плюс одно число - найденный путь (первая и последняя
его вершины должны совпадать). Гарантируется, что путь всегда существует.
|
Ввод
|
4
0 0 10 20
0 0 3 10
10 3 0 2
20 10 2 0
|
|
Вывод
|
1 3 2 4 1
|
Для отправки решений необходимо выполнить вход.
|