Dijkstra算法
每个物品对应于一结点，具有代替关系的物品用边相连，边权为优惠价格，建图。增加一个结点N＋1，连接每个结点，权值等于结点对应物品的价格，表示直接支付。题目即转化为求N＋1结点的到结点1（酋长许诺）的最短路。Dijkstra算法求解。
关于等级限制：（酋长等级未必最高）
设酋长等级为lv[1],枚举每次可行结点（lv[1]-M)~lv[1]....lv[1]~(lv[1]+M)，不在范围内的结点，设置flag为false，经过M次Dijkstra过程求得最小值，即为解。
1 #include<iostream>
2 #include<limits>
3
4 using namespace std;
5
6 const int maxN = 105;
7 const int INF = numeric_limits<int>::max();
8
9 int s[maxN][maxN];
10 int lv[maxN];
11
12 int dist[maxN];
13 bool flag[maxN];
14
15 //寻找最短路径
16 int Dijkstra(int n, int v) {
17
18 for (int i = 1; i <= n; i++) {
19 dist[i] = s[v][i];
20 }
21
22 dist[v] = 0;
23 flag[v] = true;
24
25 for (int i = 1; i < n; i++) {
26 int temp = INF;
27 int u = v;
28 for (int j = 1; j <= n; j++) {
29 if ((!flag[j] && dist[j] < temp)) {
30 u = j;
31 temp = dist[j];
32 }
33 }
34
35 if (u == 1) {
36 return dist[u];
37 }
38
39 flag[u] = true;
40
41 for (int j = 1; j <= n; j++) {
42 if ((!flag[j] && s[u][j] != INF)) {
43 int newDist = dist[u] + s[u][j];
44 if (newDist < dist[j]) {
45 dist[j] = newDist;
46 }
47 }
48 }
49 }
50 return -1;
51 }
52
53 //把不符合等级要求的物品设置为不能访问
54 void MakeFlag(int n, int f, int t) {
55
56 for (int i = 1; i <= n; i++) {
57 if (lv[i] >= f && lv[i] <= t) {
58 flag[i] = false;
59 } else {
60 flag[i] = true;
61 }
62 }
63
64 }
65
66 int main() {
67
68 int M, N;
69 int X,T,V;
70 int res, tmp;
71
72 int i, j;
73
74 while (cin >> M >> N) {
75
76 //初始化
77 for (i = 1; i <= N; i++) {
78 for (j = 1; j <= N; j++) {
79 s[i][j] = INF;
80 }
81 }
82 //输入数据
83 for (i = 1; i <= N; i++) {
84
85 cin >> s[N + 1][i] >> lv[i] >> X;
86
87 for (j = 0; j < X; j++) {
88
89 cin >> T >> V;
90 s[T][i] = V;
91 }
92 }
93
94 res = INF;
95 for (int t = M; t >= 0; t--) {
96 MakeFlag(N + 1, lv[1] - t, lv[1] + M - t);
97 tmp = Dijkstra(N + 1, N + 1);
98 if(tmp < res){
99 res=tmp;
100 }
101 }
102 cout<<res<<endl;
103 }
104 }