http://acm.pku.edu.cn/JudgeOnline/problem?id=1062
题意 ：中文的。。。。
想法 ：将冒险者看成地n + 1 个点， 进行构图，用dj 最短路解决
一个物品的价钱就是n + 1 个点 与这个物品的边，而可以代替并便宜的物品的便宜价格是代替品到这个物品的距离，这样构图完毕。
等级限制自己没有想出来，看了一些报告，最后枚举可能性，也就是说，最后要和酋长交易，那么，等级的差别就可以围绕酋长的等级来算，也就是说，如果酋长的等级是3， 等级限制是2， 那么，这次交易要想成功，可能的等级是 1 2 3 ， 2 3 4， 3 4 5 在应用dj 的时候，把等级不符合要求的点在图中去掉，也就是说，可以把它们先划分到已知的集合 s[i]里面去，这样，再进行路径扩展的时候，就不会加到这个点了。
所以，枚举可能性，重新构图，得到dj最短路的最小值， 便是结果
1 #include <stdio.h>
2 #include <string.h>
3 #define max 102
4 #define MAX 999999999
5 using namespace std;
6 int lv, n, map[max][max], tmap[max][max], rank[max], trank[max], ok[max], s[max], d[max];
7 int dj(int x){
8 int i, j, w, min;
9 memset(s, 0, sizeof(s));
10 memset(d, -1, sizeof(d));
11 for(i = 1; i <= n + 1; i++){
12 if(map[x][i])d[i] = map[x][i];
13 if(!ok[rank[i]]){
14 s[i] = 1;
15 d[i] = MAX;
16 }
17 }
18 while(1){
19 w = -1;
20 for(i = 1; i <= n + 1; i++){
21 if(!s[i] && d[i] >= 0){
22 if(w == -1 || d[i] < min){
23 min = d[i];
24 w = i;
25 }
26 }
27 }
28 if(w == -1)break;
29 s[w] = 1;
30 for(i = 1; i <= n + 1; i++){
31 if(map[w][i]){
32 if(d[i] < 0 || d[i] > d[w] + map[w][i])
33 d[i] = map[w][i] + d[w];
34 }
35 }
36 }
37 return d[1];
38 }
39 int main(){
40 int i, j, u, v, w, res, cost, nlv, t, l, r, xx;
41 while(scanf("%d%d", &lv, &n) != -1){
42 res = MAX;
43 memset(map, 0, sizeof(map));
44 memset(tmap, 0, sizeof(tmap));
45 for(i = 1; i <= n; i++){
46 scanf("%d%d%d", &cost, &nlv, &t);
47 tmap[n + 1][i] = map[n + 1][i] = cost;
48 rank[i] = trank[i] = nlv;
49 for(j = 1; j <= t; j++){
50 scanf("%d%d", &u, &cost);
51 map[u][i] = tmap[u][i] = cost;
52 }
53 }
54 trank[n + 1] = rank[n + 1] = trank[1] = rank[1];
55 for(l = lv, r = 0; l >= 0; l--, r++){
56 xx = 0;
57 memset(ok, 0, sizeof(ok));
58 for(i = l; i > 0; i--){
59 if(rank[1] - i >= 0)
60 ok[rank[1] - i] = 1;
61 }
62
63 ok[rank[1]] = 1;
64 for(j = 1; j <= r; j++){
65 ok[rank[1] + j] = 1;
66 }
67 if(res > (w = dj(n + 1)))
68 res = w;
69 }
70 printf("%d\n", res);
71 }
72 return 0;
73 }