建图思路

• 主角可设为原点, 编号为0
• 而酋长和其它人的编号设置为1~n
• 主角使用金币兑换物品(酋长的女儿也看做一件物品)时的直接交易价格可以看做从编号0到编号n的距离
• 每次使用其它物品交换时需要的价钱就可以看做从编号i到编号j的距离
• 等级限制, 每次遍历合法等级范围内的路径, 找到最短路
• 时间复杂度 O(n3)

C++代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;

int a[N][N], n, m; //a[i][j]记录使用物件i后还需a[i][j]可以得到物件j

int rankl[N], d[N]; //rank记录等级, d记录当前最小钱数

bool s[N];

int dijkstra(int l, int r)
{
    //初始化状态
    memset(d, 0x3f, sizeof(d));
    memset(s, 0, sizeof(s));
    d[0] = 0;

    for(int i = 0; i <= n; i++)//因为有一个原点,所以要遍历n+1次
    {
        int t = -1;
        for(int j = 0; j <= n; j++)
        {
            if(!s[j] && (t == -1 || d[t] > d[j]))
                t = j;
        }

        s[t] = true;

        for(int j = 0; j <= n; j++)
        {
            //判断物件等级是否合法
            if(rankl[j] >= l && rankl[j] <= r)
            {
                d[j] = min(d[j], d[t] + a[t][j]);
            }
        }
    }

    return d[1];
}

int main()
{
    cin >> m >> n;
    //初始化距离(money)
    memset(a, 0x3f, sizeof(a));
    for(int i = 0; i <= n; i++) a[i][i] = 0;

    for(int i = 1; i <= n; i++)
    {
        int prise, cnt;//价格, 可用其它物品交换的数量
        cin >> prise >> rankl[i] >> cnt;
        a[0][i] = min(a[0][i], prise);//防重边
        while(cnt--)
        {
            int id, cost;//物件id, 交易后的距离(money);
            cin >> id >> cost;
            a[id][i] = min(a[id][i], cost);
        }
    }

    int res = 0x3f3f3f3f;

    //设置合法等级区间, 遍历寻找等级区间中的合法路径, 寻找最小值
    for(int i = rankl[1] - m; i<= rankl[1]; i++) res = min(res, dijkstra(i, i + m));

    cout << res << endl;

    return 0;
}