洛谷P1127 词链 各位帮忙看看怎么做!!!

题目描述

如果单词X的末字母与单词Y的首字母相同,则X与Y可以相连成X.Y。(注意:X、Y之间是英文的句号“.”)。例如,单词dog与单词gopher,则dog与gopher可以相连成dog.gopher。

另外还有一些例子:

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

连接成的词可以与其他单词相连,组成更长的词链,例如:

aloha.arachnid.dog.gopher.rat.tiger

注意到,“.”两边的字母一定是相同的。

现在给你一些单词,请你找到字典序最小的词链,使得这些单词在词链中出现且仅出现一次。

输入输出格式

输入格式:
第一行是一个正整数n(1 ≤ n ≤ 1000),代表单词数量。

接下来共有n行,每行是一个由1到20个小写字母组成的单词

输出格式:
只有一行,表示组成字典序最小的词链,若不存在则只输出三个星号“***”。

输入输出样例

输入样例#1:
6
aloha
arachnid
dog
gopher
rat
tiger
输出样例#1:
aloha.arachnid.dog.gopher.rat.tiger
说明

对于40%的数据,有n≤10;

对于100%的数据,有n≤1000。

/*
此题难度是提高+/省选-
蒟蒻很无奈……
最好有思路和代码!拜托拜托!
*/

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问