The Toll! Revisited

**题目描述：** Sindbad 卖了66个银勺子到Samarkand（城市名）。卖的过程是很轻松的，但是运送这些货物却是一个麻烦事。 这些物品将全部从陆地上运送，中途会经过几个城镇或村庄。进去每一个城镇或村庄都需要一定的路费，离开的时候没有路费。进入村庄只要缴纳所带的1个物品，进入城镇的费用为身上所带的物品的二十分之一（取上整），举一个例子：假如你进一个城镇带了70个勺子，你需要缴纳4个勺子。 这些村庄或城镇位于险恶复杂的地形之间，所以你不能回避他们。 以下图中，方形代表城镇，圆形代表村庄 例1（图1）：Sindbad为了带66个勺子去Samarkand，需要经过一个城镇和两个村庄，则需要带76个勺子 （A，4个；b，1个；c,1个；S，4个；剩下的交付，66个）。 例2（图2）：如果你有39个物品，到达X的最好的路径为A→b→c→X（在左图上由箭头所示）。如果你有10个物品，到达X的最好路径为 A→D→X（如右图）。 计算这些路费是简单的，但找到最少路费的路径就十分有挑战性了。最优的路径取决于的带的物品。对于最多20个的物品，村镇收费相同，对于更大的数目，就要避免走城镇，而去选择村庄。就像例2。 你的任务是写一个程序解决Sindbad的问题。考虑到要送到某一城镇或村庄的物品数量和路线图，你的程序必须确定在旅途开始时最优路线所需的物品总数。你还得找到最优的路线。如果有多条路线，输出字典序最小的那一条。 **输入：** 输入由几组数据组成。每组数据由两个部分组成：路线图和交付细节。 第一行的路线图包含一个整数 n ，表示图中路的个数n。 接下来的每一行都包含两个字母，表示一条道路的两个端点。大写字母表示城镇；小写字母表示村庄。道路可以朝任一方向行驶。 在路线图之后是一行关于交付细节的数据。这一行包含三个部分：一个整数p，表示必须交付给顾客的物品，一个字符是出发点，一个字符是目的地。路线图保证可以使物品交付。 最后一组数据后面跟着数字‘-1’。 **输出：** 输出由三行组成。 第一行显示数据大小写编号。 第二行显示旅途开始时所需的物品数。 第三行根据上面的问题语句显示路径。 路径包含了Sindbad在他的旅程中经过的所有城市或村庄的名字。路径中的两个连续的城市或村庄名称用连字符分隔。 数据范围： $n\geq0$ $1< p <10^{9}$

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1478 [PDF](https://uva.onlinejudge.org/external/105/p10537.pdf) 



1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1

Case 1:
20
a-Z
Case 2:
44
A-b-c-X