1064: 2010欧洲西南分区赛：Assembly line时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 0
The input consists of several test cases. Each test case begins with a line containing a natural number k
(1 <= k <= 26), followed by a line with k symbols (characters in [a-z]) separated by spaces. The following k
lines contain the assembly table: the i-th line has k pairs of the form time-result, where time is an integer
between 0 and 1 000 000 inclusive, and result a symbol belonging to the preceding set. The j-th pair in the
i-th line represents the time to compose pieces of types represented by the i-th and j-th symbols, along with
the type of the resulting piece. After the table, a line with an integer n indicates the number of lines that
follow, each line being a string of at most 200 symbols. Each of these lines is a sequence of components that
need to be assembled together in the right order.
The input will nish with a line containing 0, which should not be processed.
For each test case, print n lines, each with an integer time and a symbol result in the format time-result.
Each line represents the minimum time and the type of the resulting piece for the corresponding case in the
input. In case of a tie among several possible results with the same minimum time, choose from among those
the piece whose type letter appears rst in the line that contained the k symbols at the beginning of the test
case. (For example, if that line was a c b and both c and b can be obtained with minimum cost 5, print 5-c).
There must be an empty line between the output of di erent test cases.
2 a b 3-b 5-b 6-a 2-b 2 aba bba 2 m e 5-e 4-m 3-e 4-m 1 eme 0
9-b 8-a 7-m