poj1724 Roads
经过无数TLE，终于让我用超级广搜过了这一题
（这题其实和sicily的1702差不多思路）。这题的主要难点有两个，1.存放图，2.剪枝。由于同一对点有可能有多条边，所以直接用二维数组是不可行的。然后最容易想到的是用邻接表。然后就是搜索了。搜索的话，我是用一个二维数组dist[i][cost]来记录从原点到i这一点耗费为cost时的最短路径。这样一来，最终的结果就是dist[n][]中的最小值。剪枝方法就是：当当前结点的的距离小于dist[][]相应值时，才把结点放入队列里面，当然不能忘记的是当前的金钱耗费不能大于k。但是仅仅这样是不够了。这样只会TLE。整个上午就纠结在如何剪枝上，结果还是没什么收获，就去吃饭&看动漫，看完之后突然灵机一闪，发现可以用一个变量minimum记录d[n][]中的最小值，然后如果当前的距离如果不小于minimum的话，就不能加入扩展队列。加上这个剪枝后，终于AC了～哈哈