本文共 1816 字，大约阅读时间需要 6 分钟。
分析:
现在我们假设没有等级限制,且有A,B,C共3种商品且A,B,C的原价分别为10000,9000,8000且A可以由B物品加上优惠价7000换取,A还可以由C物品加上优惠价1000换取. 我们在纸上把这个图画出来,然后添加一个0号节点.
从0号节点到A,B,C的有向边花费为A,B,C 3物品直接购买(不用物品+优惠价)的价格.比如从0到A花费10000.
然后比如A物品 可以用B物品+7000来换取,那么从B到A物品有一条有向边,花费为7000.从C到A有一条花费1000的有向边.
其实上面建立的图从0号节点到A或B或C的一条路的总花费就是购买A,B,C物品的一种可能总花费了.
那么我们想要购买A物品的最小花费是多少呢? 明显可以看出从0号节点到A物品的最短路径就是最小花费了.
最晦涩难懂就是这个等级限制了。本来想拿这道题入门写一下Dj算法，没想到被这个限制折磨好久~。
等级限制：
假设M=1，那么a，b，c，d等级分别为 1， 2， 3，4。如果从b那里买了，然后可以去c那里买，但是不可以去d那里买了，因为d和b相差2，如果前面已经去c那里买了，a也不能买了，因为ac相差2。
所以我们只需枚举所有的顶点的等级，然后求若干次最短路，每次只访问等级在[x,x+M]范围内的点，最后输出d[1]（到他丈母大爷那里买）的最小值。
#include #include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3fstruct edge{ int to, cost;};vector G[105];//人家只想练练用邻接表的dj算法，谁知道这是一道浙江省赛选拔题typedef pair P;int M, N;int level[105];int d[105];void dijskra(int s,int min_value){ priority_queue , greater >que; fill(d, d + N + 1, INF); d[s] = 0; que.push(P(0, s)); while (que.size()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first)continue;//此时在其他点中更新了，也就是用过了。 for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { if (v == 0 || (level[v]>=min_value&&level[v]<=min_value+M)&& (level[e.to] >= min_value&&level[e.to] <= min_value + M)) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } }}int main(){ while (cin >> M >> N) { for (int i = 1; i <= N; i++) { int P, X; cin >> P >> level[i] >> X; edge tmp0 = { i,P }; G[0].push_back(tmp0); while (X--) { int T, V; cin >> T >> V; edge tmp = { i,V }; G[T].push_back(tmp); } } int ans = INF; level[N + 1] = INF;//方便去重 for (int i = 1; i <= N; i++) { if (level[i] == level[i + 1])continue;//简单去重吧，发现排序后再去重，时间反倒增加了 dijskra(0, level[i]); ans = min(ans, d[1]); } cout << ans << endl; }}
转载地址：http://kuyci.baihongyu.com/