昨天看到其他部门的技能鉴定题目，相对我们部门偏应用的题目，他们的相对更加偏重算法。题目描述如下：

有一种单词接龙的游戏，就是连续的两个单词，第一个单词的尾要和第二个单词的头是一样的。
例如: cat tell log google就是一个单词接龙。

定义最少单词接龙是单词个数最少的接龙，定义最短单词接龙是单词字母个数总和最少的接龙。 假设所有单词都是由小写字母组成，现在给定一堆单词，给定龙头和龙尾，求出最少单词接龙和最短单词接龙。

当时在招聘，一时也没反应过来。下午回来的时候，仔细一想，这不就是最短路径问题么?

把26个小写字母看成是结点，那么每个单词就是从某个结点到另外一个结点的单向路径。
上面的接龙如果在加上单词gc, cookie，就是下面的图表示:

最少单词接龙，就是每条路径的权值为1，求两个结点之间的最短路径。
最短单词接龙，就是每条路径的权值为单词的长度，求两个结点之间的最短路径。

另外，关于一些特殊情况和注意点:

对于存在多个单词，他们的首尾字母相同的话，只记录长度最短的为路径的权值即可。

结点的存储可以不用链接表，因为只有26个字母，用二维数组即可，实时增加单词也容易处理。

求最短路径的算法，参考经典的Dijkstra最短路径算法，这里就不详述了。 关于Dijkstra，可以参考百度百科中的条目