Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Difficulty Gamma
Дан граф без петель и кратных рёбер, все рёбра имеют вес, выражающийся
натуральным числом. Требуется в этом графе найти путь, проходящий
по всем вершинам (причем по каждой - ровно один раз), и в конце
возвращающийся в начальную вершину, при этом суммарный вес всех
рёбер в этом пути должен быть минимально возможным.
Ввод
На входе записано сначала число 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
|
Для отправки решений необходимо выполнить вход.
|