АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

799. Задача коммивояжера - 9

Ограничение времени: 2 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дан граф без петель и кратных ребер, все ребра имеют вес, выражающийся
натуральным числом. Требуется в этом графе найти путь, проходящий
по всем вершинам (причем по каждой - ровно один раз), и в конце
возвращающийся в начальную вершину, при этом суммарный вес всех
ребер в этом пути должен быть минимально возможным.

Входные данные
Во входном файле записано сначала число N (3<=N<=9). Затем идет
матрица смежности графа (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

Статистика Послать на проверку Обсуждение задачи Автор/источник: olympiads.ru
Учебные курсы / Задачи с olympiads.ru /
798. 274 - Ребус-3 799. 800. 276 - Задача коммивояжера - 13 801. 277 - Универсальный ребусорешатель 802. 278 - Ханойская башня
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.