题目大意是说有N个物品，每个物品都有自己的价格，但同时某些物品也可以由其他的（可能不止一个）替代品，这些替代品的价格比较“优惠”，问怎么样选取可以让你的花费最少来购买到物品1
由于有N个物品，我们就可以把它们看作是N个点，从其他点到他的优惠关系视做边，又因为最后总是要找到物品1，所以可以看作是从起点0，到将物品1作为终点的最小路劲。然后由于题目是说，这条路劲上不能有两个的等级差超过M，所以我们可以枚举最小等级，将每个点视作最小等级，这样的话就不会掉解。
又由于我们是枚举的最小等级，所以源点0到其他每个点的边的权值就要赋值为那个点的价格，降等级比最小等级要大，或者差距大于M的其他点标记为不合法（也就是不可以走），然后在从合法的路劲中找出最小花费。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<map> 5 #include<vector> 6 #include<set> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 #include<stdlib.h> 11 using namespace std; 12 #define MAX(a,b) (a > b ? a : b) 13 #define MIN(a,b) (a < b ? a : b) 14 #define mem(a) memset(a,0,sizeof(a)) 15 #define MAXN 105 16 #define INF 1000000007 17 18 int Price[MAXN],Edge[MAXN][MAXN],Level[MAXN]; 19 int vis[MAXN], d[MAXN]; 20 int N,M,ans; 21 22 void init() 23 { 24 mem(Price); mem(Level); 25 for(int i=0;i<=N;i++) 26 { 27 for(int j=0;j<=N;j++) 28 { 29 Edge[i][j] = INF;//初始化每条边都是不连通的 30 } 31 } 32 } 33 34 void read() 35 { 36 int i,j,X,T,TP; 37 for(i=1;i<=N;i++) 38 { 39 scanf("%d%d%d",&Price[i], &Level[i], &X); 40 for(j=0;j<X;j++) 41 { 42 scanf("%d %d", &T, &TP); 43 Edge[T][i] = TP;//记录边 44 } 45 Edge[0][i] = Price[i]; 46 } 47 } 48 49 int dijkstra() 50 { 51 for(int i=1;i<=N;i++)d[i] = Price[i];//源点0到每个点的权值赋为这个点的价格 52 for(int i=1;i<=N;i++) 53 { 54 int temp = INF,x; 55 for(int j=1;j<=N;j++)if(!vis[j] && d[j]<=temp)temp = d[x = j]; 56 vis[x] = 1; 57 for(int j=1;j<=N;j++)if(d[x]+Edge[x][j] < d[j] && !vis[j])d[j] = d[x]+Edge[x][j];//要从合法的物品中选取，加上!vis[j] 58 } 59 return d[1];//这里找到的最小值是未知起点的最小值 60 } 61 62 int main() 63 { 64 while(~scanf("%d %d", &M, &N)) 65 { 66 init(); 67 read(); 68 ans = INF; 69 for(int i=1;i<=N;i++) 70 { 71 int minLevel = Level[i];//将目前的点视作等级最高的点 72 for(int j=1;j<=N;j++) 73 { 74 if(Level[j] - minLevel > M || minLevel > Level[j])vis[j] = 1;//如果有比它还低的点，或者差超过M，视为不合法 75 else vis[j] = 0; 76 } 77 int now = dijkstra(); 78 ans = MIN(ans, now); 79 } 80 printf("%d ", ans); 81 } 82 return 0; 83 }