昂贵的聘礼 POJ

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

Input

输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格"。

Output

输出最少需要的金币数。

Sample Input

Sample Output

5250

思路：由与是到1的最短价钱，而且倒序的思路过于麻烦，因此可以另建立一个0点，让0到其他点的价钱为物品初始价钱，而其他点之间的价钱为优惠价。对于等级关系，因为题意说的是
整个兑换路径中最高等级与最低等级之间的差别不能超过m，因此需要遍历所有情况，让0点作为所有的物品的等级，并以0点的等级为最高等级，进行遍历，如果超过等级则让这个点vis
标记。对遍历的所有路径进行操作后，选取最低价钱的即为答案。

代码：

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 
 22 struct node
 23 {
 24     //p价格，l等级，x可交换物品数
 25     int p,l,x;
 26     //可交换物品的编号
 27     int t[100];
 28     //可交换物品后的优惠价
 29     int v[100];
 30 };
 31 //存放物品的信息
 32 node no[100];
 33 //存放两点之间的价钱
 34 int ma[100][100];
 35 //判断物品是否市最小的
 36 int vis[100];
 37 //各点与起点的最短价钱
 38 int dis[100];
 39 //m等级差，n物品数
 40 int m,n;
 41 void dijkstra()
 42 {
 43     //初始化最小等级为初始价钱
 44     for(int i=1;i<=n;i++)
 45     {
 46         dis[i]=no[i].p;
 47     }
 48     //n-1次遍历
 49     for(int i=1;i<n;i++)
 50     {
 51 
 52         int mi=INF;
 53         int k;
 54         //寻找到起点最小的价钱
 55         for(int j=1;j<=n;j++)
 56         {
 57             if(!vis[j]&&dis[j]<mi)
 58             {
 59                 mi=dis[j];
 60                 k=j;
 61             }
 62         }
 63         //标记
 64         vis[k]=1;
 65         //如果最小的是第一件物品，则表示从0到1的最低价钱以找到，不需要遍历了
 66         if(k==1)
 67         {
 68             break;
 69         }
 70         //更新数据
 71         for(int j=1;j<=n;j++)
 72         {
 73             if(!vis[j]&&dis[j]>dis[k]+ma[k][j])
 74             {
 75                 dis[j]=dis[k]+ma[k][j];
 76             }
 77         }
 78     }
 79 }
 80 int main()
 81 {
 82     scanf("%d %d",&m,&n);
 83     //初始化为最大值
 84     memset(ma,INF,sizeof(ma));
 85     for(int i=1;i<=n;i++)
 86     {
 87         scanf("%d %d %d",&no[i].p,&no[i].l,&no[i].x);
 88         //物品与第0各物品的价钱
 89         ma[0][i]=no[i].p;
 90         for(int j=0;j<no[i].x;j++)
 91         {
 92             scanf("%d %d",&no[i].t[j],&no[i].v[j]);
 93         }
 94     }
 95     //遍历，存放在等级差可以交换的物品
 96     for(int i=1;i<=n;i++)
 97     {
 98         for(int j=0;j<no[i].x;j++)
 99         {
100             if(abs(no[i].l-no[no[i].t[j]].l)<=m)
101             {
102                 ma[no[i].t[j]][i]=no[i].v[j];
103             }
104         }
105     }
106     //ans表示当前最小值
107     int ans=INF;
108     for(int i=1;i<=n;i++)
109     {
110         memset(vis,0,sizeof(vis));
111         vis[0]=1;
112         //s当前的等级
113         int s=no[i].l;
114         //遍历初始vis将等级差过大的标记
115         for(int j=1;j<=n;j++)
116         {
117             if(i!=j)
118             {
119                 //物品等级大于s或太小的标记
120                 if(no[j].l>s||no[j].l<s-m)
121                 {
122                     vis[j]=1;
123                 }
124             }
125         }
126         dijkstra();
127         //最小值
128         ans=min(ans,dis[1]);
129     }
130     printf("%d
",ans);
131 }