bzoj#P3045. 电话线路
电话线路
题目描述
Rainbow 和 Freda 终于走出了幻象迷宫,不过经历了汪星人的一场入侵,Freda 的城堡和 Rainbow 的城堡之间的电话线路出了故障,使得只有满足某种要求的两个电话号码之间才可以直接通信。
每台电话都有一个独一无二的号码,用一个十位的十进制数字串表示。电话 和 之间能直接通信,当且仅当“ 与 之间仅有一个数字不同”,或者“交换 的某两位上的数字后, 与 相同”。而 、 之间建立通信联系所需要的时间为 ,其中 表示 、 的最长公共前缀的长度, 越大,通信时间越快, 是个常数数组。
另外,如果 、 能通信,、 能通信,那么 、 也能借助b来通信。、 借助 建立通信联系所用时间是 。
现在 Freda 想给 Rainbow 打电话,请你告诉 Freda,她最快需要多少时间才能与与 Rainbow 建立通信联系?
输入格式
第一行一个整数 ,表示电话号码的个数。
第二行 个整数,第 个整数表示 ,即当两个能够直接通信的号码的最长公共前缀为 时,二者之间建立通信联系所需的时间。
接下来 行每行一个整数表示电话号码。第一个是 Freda 的电话号码,第 个是 Rainbow 的电话号码。
输出格式
一个整数,表示所求时间。若 Freda 和 Rainbow 不能建立通信联系,输出 -1
。
样例输入
5
100 10 10 10 1 1 1 1 1 1
9123493342
3123493942
9223433942
3223493942
9223433945
样例输出
211
数据规模与约定
对于100%的数据,保证 ,每个电话号码是一个独一无二的十位十进制数字串, 。
题目来源
Poetize7