← 返回题目列表

AtCoder · yuha_c88_d

D. 冰柱上的圣剑

中文机器翻译题面 查看原题
実装難易度★★★☆☆
谜题难度★☆☆☆☆

問題文

勇者一行人来到了传说中的圣剑沉睡的冰之洞窟。

迈入地下城最深处的房间时,
眼前出现了一个横向大裂缝,脚下是悬崖。
当勇者望向房间深处时,看见对岸安放着传说中的圣剑。
裂缝中竖立着几根柱子,悬崖和柱子之间架有冰桥。
冰桥可以双向通行,
但一旦通过,就会崩塌而无法再次通行。

勇者一行人能从所在的悬崖渡到安放圣剑的悬崖,
并且还能返回吗?

入力

输入是按以下格式从标准输入给出的。
N
S_1
S_2
...
S_N
M
A_1 B_1
A_2 B_2
...
A_M B_M
C
D
  • 1 行包含悬崖及柱子的总数 N (3 ≦ N ≦ 8) 。 表示
  • 2 从线 N 行 i 在线 i 第几个悬崖或柱子的名称 S_i 。 表示
    • S_i 由大写英文字母组成。
    • S_i 的长度 |S_i| 是 您也可以写 1 ≦ |S_i| ≦ 20 很满意。
    • i ≠ j 什么时候 S_i ≠ S_j 有保证。
  • N + 2 行包含悬崖和柱子之间悬挂的冰桥数量 M (3 ≦ M ≦ N (N - 1) / 2) 。 表示
  • N + 3 从线 M 行 i 在线 i 第几座冰桥两端的悬崖或柱子名称 A_i、 B_i 。 表示
    • 保证某座冰桥的两端不会连接到同一悬崖或柱子。
    • 保证不会有多座冰桥悬挂在同一对悬崖或柱子之间。
  • N + M + 3 行包含勇者一行所站的悬崖名称 C 。 表示
  • N + M + 4 行包含圣剑所在的悬崖名称 D 。 表示
    • C ≠ D 有保证。
  • 注意,在输入中悬崖和柱子被视为相同。

出力

将满足条件的路线上的悬崖或柱子名称连接起来 1 行输出。
连接名称时,省略末尾勇者一行所站的悬崖名称。
如果可以考虑多种解,则输出经过桥数量最少的路线。
如果有多条经过桥数量最少的路线,
则将连接后的字符串按字典顺序比较,输出最小的一个。
在输出末尾插入换行符。
保证一定存在满足条件的路线。

入力例 1

6
MER
A
AS
U
B
AM
7
MER A
A B
B AM
MER AS
AS AM
MER U
U AM
MER
AM

出力例 1

MERASAMU

入力例 2

6
AB
CD
EF
GH
IJ
KL
6
AB CD
CD EF
EF GH
GH IJ
IJ KL
KL AB
AB
GH

出力例 2

ABCDEFGHIJKL