logo AlgoBeat OnlineJudge
登录 注册

#102354. [BZOJ 2354] 另类汉密尔顿路径

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

无向图中的汉密尔顿是指一条路径,它经过每个点有且仅有一次。每条汉密尔顿路径的 权值定义为这条路径中每条边的权值之和。这是最近 WZK 教小 Y 学的图论知识,现在 WZK 想检验一下小Y的举一反三的能力,提出了以下问题: 有一个n 个顶点的无向图(顶点从 0到 n-1 标号),它的每一个顶点都标有一个字符串 label[i] ,两两顶点间都存在一条边,一条从 i 到 j 的 边 的 权 值 定 义 为 length(label[i])^2+length(label[j])^2-length(LCP(label[i],label[j]))^2,LCP指的 是两个字符串的最长公共前缀。现在,要求一个从顶点 0出发,到顶点 1结束的权值最小的 汉密尔顿路径。

输入格式

第一行,一个整数 n (2<=n<=50)。 接下来n行,每行一个不超过 50个字母的小写字符串 label[i],i从0到n-1。

输出格式

仅一行,为要求的汉密尔顿路径的权值。

样例

样例输入

4 
abcd 
aecgh 
abef 
aecd 

样例输出

91