Rainbow和Freda终于走出了幻象迷宫,不过经历了汪星人的一场入侵,Freda的城堡和Rainbow的城堡之间的电话线路出了故障,使得只有满足某种要求的两个电话号码之间才可以直接通信。
每台电话都有一个独一无二的号码,用一个十位的十进制数字串表示。电话a和b之间能直接通信,当且仅当“a与b之间仅有一个数字不同”,或者“交换a的某两位上的数字后,a与b相同”。而a、b之间建立通信联系所需要的时间为cost[ lcp(a,b) ],其中lcp(a,b)表示a、b的最长公共前缀的长度,lcp(a,b)越大,通信时间越快,cost[]是个常数数组。
另外,如果a、b能通信,b、c能通信,那么a、c也能借助b来通信。a、c借助b建立通信联系所用时间是cost[ lcp(a,b) ]+ cost[ lcp(b,c) ]。
现在Freda想给Rainbow打电话,请你告诉Freda,她最快需要多少时间才能与与Rainbow建立通信联系?