Задача №112639. Самый дешёвый тур
Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, можно ли запланировать замкнутый маршрут (который начинается и заканчивается в одном и том же городе), в котором ровно K перелётов. Среди всех таких маршрутов Вася хочет выбрать самый дешёвый. Напишите программу, которая находит самый дешевый замкнутый маршрут, состоящий из K перелётов.
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 8 ). В следующих N строках записано по N неотрицательных целых чисел (не превышающих 1000), разделённых пробелами – элементы весовой матрицы графа, который описывает схему авиационных сообщений. Элемент на пересечении строки i и столбца j означает стоимость перелёта между городами i и j. Ноль указывает на отсутствие прямого рейса. В последней строке вводится значение K (2 ≤ K ≤ 8).
В первой строчке выводится стоимость оптимального перелёта, а во второй - последовательность городов, которые нужно посетить. Нумерация городов начинается с единицы. Последовательность посещаемых городов должна быть записана, начиная с города с наименьшим номером на этом маршруте. Если найдено несколько подходящих маршрутов одинаковой стоимости, нужно выбрать из них такой маршрут, в котором на каждом шаге выбирается следующий город с наименьшим возможным номером. Маршрут не должен проходить дважды через один и тот же город. Если ни одного подходящего маршрута нет, нужно вывести число 0.
5 0 2 3 5 0 2 0 4 0 1 3 4 0 6 3 5 0 6 0 0 0 0 0 4 0 3
9 1 2 3 1