P1127 词链

    • 371通过
    • 1.9K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论 搜索
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    另外还有一些例子:

    dog.gopher

    gopher.rat

    rat.tiger

    aloha.aloha

    arachnid.dog

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

    aloha.arachnid.dog.gopher.rat.tiger

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

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

    输入输出格式

    输入格式:

    第一行是一个正整数$n(1 \le n \le 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$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。