5634번 - Warp Speed II 다국어

In the not-so-distance future, space engineers can invent a new technology for traveling through space and name it as “warp-drive”. This warp-drive can make a spaceship travel faster than light speed. It works by bending an amount of distance in space and make a ship travel through that bended space in a single “hop”. To travel through space, a spaceship (that is equipped with this warp-drive) may have to perform more than one hop between the beginning and the ending points. The amount of energy/power to hop depends on the current state/configuration of the warp-drive. And some amount of energy is also consumed in order to prepare or switch to any warp-drive state.

Suppose that you are an engineer on a battle spaceship. Your duty is to control/configure the warp-drive so that it will consume as less energy as possible for any traveling. For each traveling, you will be provided with a sequence of hops, which you have to find a corresponding sequence of warp-drive configurations that use the lowest energy.

In order to accomplish your duty, you have to build a computer program to find the lowest energy of warp-drive configuration sequence for any given hop sequence based on two tables of warp-driver energy consumptions. The first table shows the energy for switching between any two states. The second table shows the energy consumption related to warp-drive states and hops.

Input is a standard input which consists of 4 parts, separated by a blank line.

The first part defines the sizes of warp-drive states and hop types.

• It contains of only one line. This line contains 2 numbers separated by a space. These 2 number are
  • Size of warp-drive states(N), which is between 1 and 100.
    • The state id is starting from 0 to N-1.
    • The first state (id #0) is the idle state. At this and only this state, the warp-drive can't perform any hop. (It is the default starting and ending state for any output state sequence.)
  • Size of different types of hops(H), which is between 1 and 1,000.
    • The hop id from 0 to H-1.

The second part is a table showing the energy for switching warp-drive states. The table size is N rows and N columns, which contains N² energy values.

• There are N lines. Each line contains N energy values. These values are between 1 and 100.
• Each energy value can be indexed by its row and column. The row and column indexes are the state ids of the current and next warp-drive states respectively. Please be notified that these two indexes are starting from 0.
  • For example, the value at (row index, column index) = (5,0) is the energy for switching warp-drive state from number 5 to 0. (This value is the first number in the sixth line.)

The third part is a table showing the energy consumption in performing hops for each state drive.

The table size is N rows and H columns, which contains N by H values.

• There are N lines. Each line contains H energy values. These values are between 1 and 100.
• Each energy value can be indexed by its row and its column. The row index is the id of the current warp-drive state. The column index is the id of the hop. Please be notified that these two indexes are starting from 0.
  • For example, the value at (row index, column index) = (1,9) is the energy for warp-drive at state #1 to perform hop #9 . (This value is the tenth number in the second line.)
  • Please be notified that in the very first line of this part, which corresponds to the state #0 or the idle state, all numbers are zeros. This rather means that it can't perform any hop in this state.

The fourth part is a set of hop sequences. The number of sequences in this set is between 1 and 1,000.

• The number of lines is 1 up to 1,000.
• Each line in this part contains one hop sequences.
• The number of hops in a sequence is between 1 and 1,000.
• Each hop is a number (starting from 0 to H-1) and is separated with space.

The blank line after the fourth part is the termination of the input.

For each hop sequence in the fourth part of the input, write 2 parts of output as follows

• In the first line, write the total amount of energy which must be minimum.
• In the following line, write the solution. The solution contains a sequence of warp-drive states corresponds to the given hop sequence. (The size of input and output sequence must be equal.) If there are two or more possible solutions which consumes the same amount of energy, write only the sequence which contains the lowest states comparing from left to right.

There are 15 lines in the sample input and 4 lines in the sample output.

In the first sample output (solution for input line #13), the minimum total energy is 9. The warpdrive state sequence is [3 2] or [0- 3 2 -0]. There are 3 state switchings from 0 → 3, 3 → 2, and 2 → 0, which consumes 1 + 1 + 2 = 4. And two hops (0 and 4) at state 3 and 2 respectively, which consumes 4 +1 = 5. So the total energy is 4 + 5 = 9.

In the last sample output, the minimum energy is 23. The solution is [0- 1 1 2 3 -0] which draws 23 energy in total.