程序设计在线评测(Online Judge)

2017年湖南科技大学大学生计算机程序设计竞赛初定于12月17日举行!有意参赛请加QQ群“湖科大程序设计校赛群(369699377)”

问题 1064. -- 2010欧洲西南分区赛:Assembly line

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

提示

来源

[提交][状态][讨论版]