莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 核心：每个仆人物品向主人物品连一条边，难点就是建图
2. 把所有区间枚举一边求最小值
3. 在一区间内，求虚拟原点到 1 号点的最短路

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int m,n;
int w[N][N],level[N];
int dist[N];
bool st[N];

//求 0 号点到 1 号点的最短距离
int dijkstra(int down,int up)
{
    memset(st,0,sizeof st);

    memset(dist,0x3f,sizeof dist);
    dist[0]=0;

    for(int i=0;i<=n;i++)
    {
        int t=-1;
        for(int j=0;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;

        st[t]=true;

        //只有在等级限制范围内才能交换
        for(int j=1;j<=n;j++) 
            if(level[j]>=down&&level[j]<=up)
                dist[j]=min(dist[j],dist[t]+w[t][j]);
    }

    return dist[1];
}

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

    memset(w,0x3f,sizeof w);

    //建图，仆人物品向主人物品连一条边
    for(int i=1;i<=n;i++)
    {
        int price,cnt;
        cin>>price>>level[i]>>cnt;
        w[0][i]=price;

        while(cnt--)
        {
            int id,cost;
            cin>>id>>cost;
            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;
}