Невозможно понять. Задача "Путешествие продавца"

Задача 2. Путешествие продавца

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 мегабайта


Как обычно, кому-то надо продать что-то во многих городах. Имеются
города, представленные как M множеств (столбцов) по N городов (строк) в
каждом.

Продавец должен посетить ровно по одному городу из каждого
множества, затратив на это как можно меньшую сумму денег. Он должен
посетить сначала город из первого множества, затем из второго и так далее,
строго по порядку. Он может выбирать начало своего путешествия. Число,
которое находжится в i-й строке и j-м столбце означает стоимость
перемещения из предыдущего места в этот город. Однако, имеется
ограничение на перемещения: он может перемещаться из города в i-й строке
только в города следующего столбца, находящиеся в одной из строк i -1, i, i+1,
если такие строки существуют.
Иногда, чтобы заставить посетить продавца какой-то город, ему
доплачивают, то есть, стоимость перемещения может быть отрицательной.
Требуется определить наименьшую стоимость маршрута и сам маршрут.

Формат входных данных
N M
C11 C12 … C1M
C21 C22 … C2M
… … … …
CN1 CN2 … CNM
3 ≤ N ≤ 150
3 ≤ M ≤ 1000
-1000 ≤ Cij ≤ 1000

Формат выходных данных

Первая строка — список через пробел номеров строк (начиная с 1) из M
посещенных городов.
Вторая строка — общая стоимость поездки.
Если имеется несколько маршрутов с одной стоимостью, требуется
вывести маршрут, наименьший в лексикографическом порядке.
Начинать и заканчивать маршрут можно в любой строке.

0

Сообщение от dimpa Невозможно понять

Что именно?

В целом это так называемая "задача коммивояжера". Не ленимся и пользуемся поиском чтобы найти решение.

0