Warp Speed II
В недалеком будущем космические инженеры могут разработать новую технологию для путешествий в космосе, названную «варп-двигатель». Этот двигатель способен перемещать космический корабль быстрее скорости света, изгибая пространство и позволяя кораблю перемещаться через это изогнутое пространство за один «прыжок». Для путешествия в космосе корабль, оснащенный варп-двигателем, может совершить несколько прыжков между начальной и конечной точками. Энергия, необходимая для прыжка, зависит от текущего состояния варп-двигателя, и некоторая энергия также расходуется на подготовку или переключение между состояниями двигателя.
Цель
Представьте, что вы инженер на боевом космическом корабле. Ваша задача — управлять варп-двигателем так, чтобы минимизировать потребление энергии во время путешествия. Для каждого путешествия вам будет дана последовательность прыжков, и ваша задача — найти оптимальную последовательность конфигураций варп-двигателя, которая потребляет минимальное количество энергии.
Для выполнения этой задачи вам нужно создать программу, которая определяет минимальную энергию для последовательности конфигураций варп-двигателя, основываясь на двух таблицах энергопотребления. Первая таблица показывает энергию, необходимую для переключения между состояниями, а вторая — энергопотребление для каждого состояния двигателя при выполнении прыжков.
Входные данные
Входные данные поступают через стандартный ввод и состоят из 4 частей, разделенных пустой строкой.
Первая часть определяет количество состояний варп-двигателя и типов прыжков.
Она содержит одну строку с 2 числами, разделенными пробелом:
Количество состояний варп-двигателя (N), от 1 до 100.
Идентификаторы состояний варьируются от 0 до N-1.
Первое состояние (идентификатор #0) — это состояние ожидания, в котором варп-двигатель не может выполнять прыжки. Это состояние используется по умолчанию для начала и окончания любой последовательности состояний.
Количество типов прыжков (H), от 1 до 1000.
Идентификаторы прыжков варьируются от 0 до H-1.
Вторая часть — таблица энергозатрат на переключение состояний варп-двигателя. Таблица имеет размер N на N и содержит N^2 значений энергии.
Таблица состоит из N строк, каждая из которых содержит N значений энергии в диапазоне от 1 до 100.
Каждое значение энергии индексируется по строке и столбцу, которые соответствуют текущему и следующему состояниям варп-двигателя. Индексы начинаются с 0.
Например, значение в позиции (индекс строки, индекс столбца) = (5,0) — это энергия для переключения состояния варп-двигателя с 5 на 0. (Это значение — первое число в шестой строке.)
Третья часть — таблица энергопотребления для выполнения прыжков в каждом состоянии двигателя.
Таблица имеет размер N на H и содержит N на H значений.
Таблица состоит из N строк, каждая из которых содержит H значений энергии в диапазоне от 1 до 100.
Каждое значение энергии индексируется по строке и столбцу, где строка — это идентификатор текущего состояния варп-двигателя, а столбец — идентификатор прыжка. Индексы начинаются с 0.
Например, значение в позиции (индекс строки, индекс столбца) = (1,9) — это энергия для варп-двигателя в состоянии #1 для выполнения прыжка #9. (Это значение — десятое число во второй строке.)
Обратите внимание, что в первой строке этой части, соответствующей состоянию #0 или состоянию ожидания, все значения равны нулю, что означает невозможность выполнения прыжков в этом состоянии.
Четвертая часть — набор последовательностей прыжков. Количество последовательностей варьируется от 1 до 1000.
Количество строк — от 1 до 1000.
Каждая строка содержит одну последовательность прыжков.
Количество прыжков в последовательности варьируется от 1 до 1000.
Каждый прыжок представлен числом от 0 до H-1 и разделен пробелом.
Пустая строка после четвертой части обозначает конец ввода.
Выходные данные
Для каждой последовательности прыжков из четвертой части ввода выведите 2 части:
В первой строке укажите общее минимальное количество энергии.
Во второй строке укажите решение — последовательность состояний варп-двигателя, соответствующую данной последовательности прыжков. (Размер входной и выходной последовательности должен совпадать.) Если существует несколько решений с одинаковым энергопотреблением, выберите последовательность с наименьшими состояниями, сравнивая слева направо.
Дополнительные объяснения
В примере ввода 15 строк, а в примере вывода 4 строки.
В первом примере вывода (решение для строки ввода #13) минимальная общая энергия равна 9. Последовательность состояний варп-двигателя — [3 2] или [0- 3 2 -0]. Происходит 3 переключения состояний: с 0 на 3, с 3 на 2, и с 2 на 0, что потребляет 1 + 1 + 2 = 4 энергии. Два прыжка (0 и 4) в состояниях 3 и 2 соответственно потребляют 4 + 1 = 5 энергии. Таким образом, общая энергия равна 4 + 5 = 9.
В последнем примере вывода минимальная энергия равна 23. Решение — [0- 1 1 2 3 -0], которое потребляет в общей сложности 23 энергии.