#BZOJ2354. 另类汉密尔顿路径

另类汉密尔顿路径

No submission language available for this problem.

题目描述

无向图中的汉密尔顿是指一条路径,它经过每个点有且仅有一次。每条汉密尔顿路径的
权值定义为这条路径中每条边的权值之和。这是最近 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