一开始想用动态规划做，但是发现有可能有环，这样需要做许多额外的处理工作，所以使用dijkstra求单元最短路。
建图使用可交换的优惠物品做有向图，如A需要 B加上一个优惠价格valueB来交换，那么就连接一条B到A的有向边，权值为valueB。探险家设置为0点，对每个物品都有一个有向边，权值为物品的价格。
考虑到dijkstra并不好加入等级的限制，那么可以取巧地使用枚举来枚举等级范围，不满足范围的点不予考虑即可。
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 int map[101][101]; 5 int p[101], l[101], x[101]; 6 int n, m; 7 const int maxint = 20000000; 8 9 int dijkstra(int min){ 10 short flag[101]; 11 int i, j, step, minl, tmp; //"step" means the recent point in the shortest set 12 int len[101]; //the length of the path 13 for (i = 0; i <= n; i++){ 14 flag[i] = 0; 15 len[i] = maxint; 16 } 17 len[0] = 0; 18 flag[0] = 1; 19 i = 0; 20 step = 0; 21 while (i < n){ 22 minl = maxint; 23 i++; 24 for (j = 1; j <= n; j++) 25 if ((l[j] >= min)&&(l[j] <= min + m)&&(map[step][j] + len[step] < len[j])) len[j] = map[step][j] + len[step]; 26 for (j = 1; j <= n; j++) 27 if ((!flag[j])&&(len[j] < minl)){ 28 minl = len[j]; 29 tmp = j; 30 } 31 flag[tmp] = 1; 32 step = tmp; 33 } 34 return len[1]; 35 } 36 37 int main(){ 38 int i, j, t, v, maxl, tmp; 39 maxl = maxint; 40 scanf("%d %d", &m, &n); 41 for (i = 0; i <= n; i++) 42 for (j = 0; j <= n; j++) 43 map[i][j] = maxint; 44 for (i = 1; i <= n; i++){ 45 scanf("%d %d %d", &p[i], &l[i], &x[i]); 46 map[0][i] = p[i]; 47 for (j = 1; j <= x[i]; j++){ 48 scanf("%d %d", &t, &v); 49 map[t][i] = v; 50 } 51 } 52 for (i = 1; i <= n; i++){ 53 tmp = dijkstra(l[i]); 54 //printf("tmp = %d ", tmp); 55 if (maxl > tmp) maxl = tmp; 56 } 57 printf("%d ", maxl); 58 return 0; 59 }