poj-1062 dijkstra算法

这道题就是用来回忆dijkstra算法的，题目大意是我可以与多个人进行交易，目的是想娶国王的女儿（即聘礼啦），直接找国王需要10000金币的聘礼，但是可以用一个钻石加8000金币换，或者其他物品加相应金额换取。同样的钻石可以用某一物品再加相应金额换取到。除交换价格外，还要注意的是交换需要在一定等级内产生，会手动输入一个数字标示等级差M，交换的人属于不同的等级，我只能与某个人及大于他不超过M级的人们交易或者小于他不超过M的人们进行交易。输入的格式如下：
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
输出一个最少金额，可以满足国王的要求。（原价10000的聘礼），第一行的两个数据：第一个是等级差M，第二个是一共多少个物品。之后一行有三个数据，分别是价格，主人的等级，还有就是可以替代的物品数，比如上述数据第二行是10000 3 2，表示该物品价格是10000，主人等级是3，可以有两种代替方案：第一种是2号物品加8000个金币即可，第二个是三号物品加5000个金币即可，以 此类推。
这道题可以使用dijkstra算法：有个0点，所有物品的单价设为0点到物品点的权重，物品与物品之间的交换代价就是点与点之间的权重，那么等级问题该怎么办？这里就巧妙的用到了原dijkstra算法中的判断数组：因为注意到是不知道那个起点开始交易，所以遍历所有的点，选择一个点后首先进行点的选择，将等级太低的。