题意：

中文题意， 但是很难懂， 我也懒得复述了直接给链接，自己去看看， 一道很有意思的最短路

传送门

题解：

设置一个源点为0

把每样物品i的原先价格dis[i] 当作mapp[0][i]      将每样物品x的的替代品y 两者产生的优惠价格 也当作一条边mapp[y][x]

然后由此用Dijkstra算法 求出dis[1](1为酋长的承诺)

这里面有个限制条件 等级限制m 

我们可以枚举每个物品的主人的等级为最高 将不符合的人用vis[]数组标记为 true, 将符合的人标记为 false, 这样循环跑 最短路的时候就不会用到这些点了

只要跑n次最短路 就可以得出最优 的结果  

/*
Algorithm:  Dijkstra
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>

#define maxn 1005
#define mod 1e9 + 7
#define inf 0x3f3f3f3f
typedef long long ll;
#define line printf("--------------");
using namespace std;
int leval[maxn];
int mapp[maxn][maxn];
int value[maxn];
int x[maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
int dijstra() {
	for(int i = 1 ; i <= n; i++) {
		dis[i] = mapp[0][i];
	}
	int minlen;
	int now;
	for(int i = 1; i <= n; i++) {
		now = 0;
		minlen = inf;
		for(int j = 1; j <= n; j++) {
			if(!vis[j] && minlen > dis[j]) {
				minlen = dis[j];
				now = j;
			}
		}
		if(now == 0) {
			break;
		}
		vis[now] = true;
		for(int j = 1; j <= n; j++) {
			if(!vis[j] && mapp[now][j] > 0 && dis[j] > dis[now] + mapp[now][j])   //把未访问但与node（新源点）连通的点进行松弛
				dis[j] = dis[now] + mapp[now][j];
		}
	}
	return dis[1];
}
int main() {
	memset(mapp, 0, sizeof(mapp));
	memset(value, 0, sizeof(value));
	memset(vis, false, sizeof(vis));
	memset(leval, 0, sizeof(leval));
	memset(dis, inf, sizeof(dis));
	cin>>m>>n;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d %d",&value[i], &leval[i], &x[i]);
		mapp[0][i] = value[i];
		for(int j = 0; j < x[i]; j++) {
			int a, b;
			scanf("%d %d", &a, &b);
			mapp[a][i] = b;
		}
	}
	int minn = inf;
	int maxlv;
	for(int i = 1; i <= n; i++) {
		maxlv = leval[i];
		for(int j = 1; j <= n; j++) {
			if(leval[j] > maxlv || maxlv > leval[j] + m) {
				vis[j] = true;
			} else {
				vis[j] = false;
			}
		}
//		cout<<dijstra()<<"==="<<endl;
		minn = min(minn, dijstra());
	}
	cout<<minn<<endl;
	return 0;
}