Warp Speed II
У недалекому майбутньому космічні інженери можуть винайти нову технологію для подорожей у космосі, яку назвали "варп-двигун". Цей варп-двигун дозволяє космічному кораблю подорожувати швидше за швидкість світла, згинаючи певну відстань у космосі, що дозволяє кораблю переміщатися через цей зігнутий простір за один "стрибок". Для подорожі космосом корабель, оснащений варп-двигуном, може виконати кілька стрибків між початковою та кінцевою точками. Кількість енергії, необхідної для стрибка, залежить від поточного стану варп-двигуна, а також певна кількість енергії витрачається на підготовку або перемикання між станами варп-двигуна.
Мета
Припустимо, що ви інженер на бойовому космічному кораблі. Ваше завдання — налаштувати варп-двигун так, щоб він споживав якомога менше енергії під час будь-якої подорожі. Для кожної подорожі вам буде надано послідовність стрибків, для якої ви повинні знайти відповідну послідовність конфігурацій варп-двигуна, що використовує найменшу кількість енергії.
Щоб виконати своє завдання, ви повинні створити комп'ютерну програму, яка знайде найменшу енергію конфігурації варп-двигуна для будь-якої заданої послідовності стрибків, використовуючи дві таблиці енергоспоживання варп-двигуна. Перша таблиця показує енергію для перемикання між будь-якими двома станами. Друга таблиця показує енергоспоживання, пов'язане зі станами варп-двигуна та стрибками.
Вхідні дані
Вхідні дані складаються з 4 частин, розділених порожнім рядком.
Перша частина визначає розміри станів варп-двигуна та типів стрибків.
Вона містить лише один рядок з 2 числами, розділеними пробілом. Ці 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 частини виходу наступним чином:
У першому рядку напишіть загальну кількість енергії, яка має бути мінімальною.
У наступному рядку напишіть рішення. Рішення містить послідовність станів варп-двигуна, що відповідає заданій послідовності стрибків. (Розмір вхідної та вихідної послідовності має бути однаковим.) Якщо є два або більше можливих рішень, які споживають однакову кількість енергії, напишіть лише послідовність, яка містить найменші стани, порівнюючи зліва направо.
Додаткові пояснення
У першому зразку виходу (рішення для рядка введення #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 енергії.