P1613 - 词链

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：9 通过：6

如果单词 $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`

注意到，`.` 两边的字母一定是相同的。

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 $k$ 次就需要输出 $k$ 次。

第一行是一个正整数 $n$（$1 \le n \le 1000$），代表单词数量。

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

只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 `***`。

6
aloha
arachnid
dog
gopher
rat
tiger

aloha.arachnid.dog.gopher.rat.tiger

- 对于 $40\%$ 的数据，有 $n \leq 10$；
- 对于 $100\%$ 的数据，有 $n \leq 1000$。

图论基础

1613: 词链

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签