简单理解

y总的图：

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int w[N][N], n, m, level[N], dist[N], vis[N];

int dijkstra(int l, int r){
    memset(dist, 0x3f, sizeof dist);
    memset(vis, false, sizeof vis);
    // 虚拟源点0号点初始距离为0
    dist[0] = 0;
    // n个点以及虚拟源点0号点共n + 1个点！
    for(int i = 0; i < n + 1; i ++){
        int t = -1;
        for(int j = 0; j <= n; j ++)
            if(!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;

        vis[t] = true;

        for(int j = 0; j <= n; j ++)
            // 等级区间内的才可以更新
            if(level[j] >= l && level[j] <= r)
                dist[j] = min(dist[j], dist[t] + w[t][j]);
    }
    // 终点为1号点
    return dist[1];
}

int main(){
    cin >> m >> n;

    memset(w, 0x3f, sizeof w);
    // 自认为这个初始化无意义
    // for(int i = 1; i <= n; i ++) w[i][i] = 0;

    for(int i = 1; i <= n; i ++){
        int price, cnt; cin >> price >> level[i] >> cnt;
        // 虚拟源点到该点权重为price，重复边取min即可
        w[0][i] = min(w[0][i], price);
        while(cnt --){
            int id, cost; cin >> id >> cost;
            // 替代品到该点权重为cost，重复边取min即可
            w[id][i] = min(w[id][i], cost);
        }
    }
    int res = INF;
    // 等级区间必须包含一号点，否则最短路将没有一号点
    // 在包含一号点的所有区间内都做一遍最短路，取最小值即可
    for(int i = level[1] - m; i <= level[1]; i ++) res = min(res, dijkstra(i, i + m));
    cout << res << endl;
    return 0;
}