Однонаправленная задача коммивояжёра
(Время: 1 сек. Память: 16 Мб Сложность: 41%)
Задана матрица размером m×n из целых чисел. Путь начинается в любой строке первого столбца и состоит из последовательности шагов, обрывающихся в столбце n. Каждый шаг состоит в переходе из столбца i в столбец i+1 в соседнюю (по горизонтали или диагонали) ячейку. Весом пути называется сумма целых чисел, записанных в каждой из n посещенных ячеек.
Требуется написать программу, которая вычисляет путь с минимальным весом с левого края матрицы до правого.
Входные данные
Входной текстовый файл INPUT.TXT содержит в первой строке количество строк и столбцов матрицы, которые обозначаются m и n соответственно. Далее следует m строк по n чисел в каждой. Числа отделяются друг от друга пробелами. Число строк не превышает 10, столбцов – 100. Вес любого пути не будет превышать целого числа, для хранения которого потребуется больше 30 бит.
Выходные данные
Выходной текстовый файл OUTPUT.TXT должен содержать две строки. Первая строка задает путь минимальной стоимости, а вторая – соответственно стоимость этого пути. Путь состоит из последовательности n целых чисел (разделенных одним или более пробелами), задающих номера строк, из которых состоит путь минимальной стоимости. Если путей минимальной стоимости больше одного, то должен быть выведен лексикографически минимальный путь.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4 | 1 2 3 4 4 5
16 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
