АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
Textbooks FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

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

Time Limit: 2 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added 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

View Problem Statistics Submit Problem discussion Author/source: olympiads.ru
Educational Courses / Problems from olympiads.ru /
798. 274 - Ребус-3 799. 800. 276 - Задача коммивояжера - 13 801. 277 - Универсальный ребусорешатель 802. 278 - Ханойская башня
time generating 0.14 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.