你想娶酋长的女儿，但酋长要求你给一定数额金钱的聘礼。除了金钱外，酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。
容易想到这题可以将它转换为一张有向图。边权代表由A到B所需要附加的金钱。由于每个人只有一个物体，所以节点既可以代表人也可以代表人手中的物品。
我们可以很容易的看出，这题是单源最短路。可以用Dijkstra解决。
唯一遗留的问题就是等级限制。
因为线路中最高最低等级差不能超过给定值m，所以我们枚举等级区间，设酋长等级为l，则从[l-ml]枚举到[ll+m]。对于每一个区间，我们进行筛选，对不满足的点在Dijkstra使用的松弛标记数组visit[]中标记为已访问。则可以避免它参与松弛。（注意每次枚举前对它初始化。）筛选后对区间进行Dijkstra。并将结果比较替换当前最优解。直到枚举结束。