The Postal Worker Rings Once

计算机科学中的一个非常重要的组成部分就是图论算法，它们都可以追溯到欧拉和著名的哥尼斯堡七桥问题。许多优化问题都需要确定有关图推理的高效方法。 该问题就是要为邮递员确定一条路线，让他在投递所有信件的同时只走最短的距离，以节省脚力。 ## 问题描述 给定一系列的街道（由路口相互联通），你要写一个程序来确定跑遍所有这些街道所需的最小旅程。旅程结束时必须回到起点的路口。 在现实生活中的情况是一个邮递员将它的卡车停在路口，然后跑遍所有的小巷来完成投递任务（发邮件），最后回到卡车继续下一次投递任务。 穿过一条街所花费的开销是这条街长度的函数（将邮件投递入户会产生开销，行走而没有投递也会产生开销）。 在这个问题中，与一个路口相连的所有街道的数量称为这个路口的“度”。最多存在两个奇数度的路口，其它所有路口的度均为偶数，即有偶数条街道与该路口相连。 ## 输入 输入由一条或多条邮递路线构成。路线由一系列的街道名称（字符串）来表示，每条街独占一行。字符串“deadend”表示一条路线的结束，但它本身不是路线的一部分。每条街道的第一个和最后一个字母代表了这条街道的两个路口，街道名称的长度即为穿过这条街道所需的开销。所有街道的名称都由小写字母构成。 比如说，一条街道的名称为“foo”表示它的两个路口为“f”和“o”，且长度为3；另一条街道的名称为“computer”表示它的两个路口为“c”和“r”，长度为8。不存在首尾字母相同的街道，两个路口最多由一条街道直接连通。在每条邮递路线中都存在一条路径可以跑遍所有的路口，即所有路口都是连通的。 ## 输出 对应输入的每条邮递路线，应输出访问其所有街道至少一次的最短路径的开销。最短路径开销应按照输入的邮递路线的相应顺序输出。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=53 [PDF](https://uva.onlinejudge.org/external/1/p117.pdf) 



one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

11
114