题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104198067

一、内容

 某天超市搞活动，小明想买一个自己一直想买的电脑，平时需要7000，小明觉得太贵了。但活动当天，超市里的商品可以通过买其他商品获得优惠券。例如买一个键盘然后买电脑只需要5000，如果买一个鼠标买电脑只需要4000。同理，买其他商品也有这样的优惠活动。但商场出于某种目的，给每一件商品都标了等级，如果买了低于某个等级的商品，就不能够再买某些高级商品。
为了方便，商店将每一件商品从1开始编号，电脑的编号为1.每一件商品都有对应的价格p,等级l,以及所对应的优惠商品Ki和优惠价格Ri。如果两件商品等级差超过D，就不能同时购买。小明想用最少的钱买到电脑。

Input

第一行是两个整数D，t（1 <= t <= 100），分别代表等级的差距限制和商品的数量。接下来按照编号从1到t给出商品的描述。每个商品的描述开头是v、e、m（m < t），表示该物品的价格、商品的等级和对应优惠商品总数。接下来m行每行包括两个整数K和R，分别表示优惠商品的编号和对应商品优惠后价格。

Output

输出最少需要的钱。

Sample Input

2 4
7000 2 2
2 5000
3 4000
500 1 0
1000 2 1
4  100
30 2 0

Sample Output

4130

二、思路

• 建立一个超级源点0，从0建立一条边到每个物品，权值为物品的价值。代表花费多少钱就可以购买这个物品。
• 若某个物品拥有替代品，代表从替代品建立一条边到这个物品，价值为替代的价值。 代表我有了这个替代品，那么还需要花费多少就能买这个物品。
  
• 最后就是等级制度。我们可以枚举每个等级区间，每次求最短路是只能更新在这个区间里面的物品。枚举所有情况求一个最小值就可以了。 特别注意的是区间必须包含1点。 那么范围就是【L[1] - m, L[1]】

三、代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105, M = 1e4 + 5, INF = 0x3f3f3f3f;
struct E {
    int v, w, next;
} e[M];
int k, n, x, u, v, w, maxL = INF, len = 1, L[N], h[N], d[N];//L[i]代表i的等级
bool vis[N];
void add(int u, int v, int w) {
    e[len].v = v;
    e[len].w = w;
    e[len].next = h[u];
    h[u] = len++;
}
void spfa(int l, int r) {
    memset(d, 0x3f, sizeof(d));
    d[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            int w = e[j].w + d[u];
            if (l <= L[v] && L[v] <= r && d[v] > w) {
                d[v] = w;
                if (!vis[v]) vis[v] = true, q.push(v);
            }
        }
    } 
}
int main() {
    scanf("%d%d", &k, &n);
    for (int u = 1; u <= n; u++) {
        scanf("%d%d%d", &w, &L[u], &x);
        maxL = max(maxL, L[u]);
        add(0, u, w);//0号点花费w的价值就可以买
        while (x--) {
            scanf("%d%d", &v, &w);
            add(v, u, w); //v-->u 有了v花费w就可以买u 
        } 
    }
    //枚举下等级范围 求出最小的ans
    int ans = INF;
    for (int i = L[1] - k; i <= L[1]; i++) { //等级范围 肯定是要包含1点的 不然你连1都无法购买 
        //可以和[i, i + k]区间的人交易
        spfa(i, i + k);
        ans = min(d[1], ans); 
    } 
    printf("%d", ans);
    return 0;
}