uva 10537 Toll! Revisited(优先队列优化dijstra及变形)

大致题意：有两种节点，一种是大写字母，一种是小写字母。首先输入m条边，当经过小写字母时需要付一单位的过路费，当经过大写字母时，要付当前财务的1/20做过路费。问在起点最少需要带多少物品使到达终点时还有k个物品。当有多条符合条件的路径时输出字典序最小的一个。

思路：已知终点的权值，那么可以从终点向前推。求终点到起点的最短路径，然后按字典序打印路径。

比较难处理的是：向前推时前驱节点的权值计算。列个方程算算就可以了，主要时不能整除的情况。

计算前驱结点dis值的时候，同时记录(i,j)的边权值，这是打印路径的依据。