POJ - 1062 昂贵的聘礼 (迪杰斯特拉+限制)

淡淡的烟草味﹌ 2022-05-18 00:55 146阅读 0赞

#                                            昂贵的聘礼 #

### Description ###

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用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 ###

1 4
    10000 3 2
    2 8000
    3 5000
    1000 2 1
    4 200
    3000 2 1
    4 200
    50 2 0

### Sample Output ###

5250

**题意描述：**

1号商品用其他商品替代但不能超过等级限制，使花费金币最小；（求dis\[\]数组最小值但不能超过等级限制）

**解题思路：**

对于每件商品将它的等级和价格存储起来，它的替代品便宜的价格相当于商品A到B的权值，对于等级限制看的网上的题解，将所有符合的枚举出来找最小的。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    # define inf 99999999
    struct A
    {
    	int x;
    	int y;
    }q[5050];
    int map[5050][5050],book[5050],dis[5050];
    int main()
    {
    	int m,n,t,i,j,u,v,min,k,p,f;
    	while(scanf("%d%d",&m,&n)!=EOF)
    	{
    		for(i=1;i<=n;i++)
    			for(j=1;j<=n;j++)
    			{
    				if(i==j)
    					map[i][j]=0;
    				else
    					map[i][j]=inf;
    			}
    		for(i=1;i<=n;i++)//存储商品的价格和等级 
    		{
    			scanf("%d%d%d",&q[i].x,&q[i].y,&k); 
    			for(j=1;j<=k;j++)
    			{
    				scanf("%d",&f);
    				scanf("%d",&map[i][f]);//替代品为商品之间的权值 
    			}
    		}
    		p=inf;
    		for(k=q[1].y-m;k<=q[1].y;k++)//枚举全部情况 
    		{
    			memset(book,0,sizeof(book));
    			for(i=1;i<=n;i++)
    				dis[i]=map[1][i];
    			for(i=2;i<=n;i++)
    			{
    				if(q[i].y>k+m||q[i].y<k)//不符合的标记，dis数组中的值更新为无穷大 
    				{
    					book[i]=1;
    					dis[i]=inf;
    				}
    			}
    			book[1]=1;
    			for(i=1;i<n;i++)
    			{
    				min=inf;
    				for(j=1;j<=n;j++)
    				{	
    					if(book[j]==0&&dis[j]<min)
    					{
    						min=dis[j];
    						u=j;
    					}
    				}
    				if(min==inf)
    					break;
    				book[u]=1;
    				for(v=1;v<=n;v++)
    				{
    						if(dis[v]>dis[u]+map[u][v]&&book[v]==0)
    							dis[v]=dis[u]+map[u][v];
    							
    				}
    			}
    			for(i=1;i<=n;i++)
    			{
    				dis[i]=dis[i]+q[i].x;
    				if(dis[i]<p)
    					p=dis[i];
    			}
    		}
    		printf("%d\n",p);
    	}
    	return 0;
    }