题目大意

你需要花费 $w$ 元才能获得物品 1，但现在你可以通过花费 $x$ 获得物品 2 后，再花费 $k$ 元，就可以获取物品 1。然后，物品拥有等级，经过手的物品等级差距不能超过 M。

现在有 $N$ 个物品，告诉你每个物品的等级，以及每个物品直接购买所要花费的费用 $P$，以及一系列物品替换方式，请问如何花最少的钱购买到物品 $N$。

分析

一个等价问题：有 $n$ 个地方。你可以直接花费 $w_{1,n}$ 从编号为 1 的地点到达编号为 $n$ 的地点。或者先花费 $w_{1,k}$ 先到达编号为 $k$ 的地点，再花费 $w_{k,n}$ 到达编号为 $n$ 的地点。

所以，可以将物品抽象成图上的顶点。物品之间的花费抽象成图上的边。然后，创建一个虚拟点作为起点，连向图上所有的顶点，边权大小为直接购买该物品所需要的花费。最后，从虚拟点出发跑一遍最短路完成求解。

但图中还有个等级限制：我们可以直接通过枚举物品的等级范围。限定，图中可经过的顶点的等级范围。

这样做的时间复杂度为 $O(N^{3}logN)$。

示例程序

#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;
}