【日常学习】【条件最短路dij】POJ1062 昂贵的聘礼（2002年浙江省队选拔赛）题解

淡淡的烟草味﹌ 2022-08-08 03:26 120阅读 0赞

耗时三节课 充分体现出粗心酿成大错这个道理 一开始一直不知道为什么数组越界 原来是minn和ninj写反了 后来又因为读入函数出问题 反复调试 今后一定要注意

题目还是放上吧：

题目描述 Description

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

为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的“优惠”Vi。如果两人地位等级差距超过了M，就不能“间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

输入描述 Input Description

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

输出描述 Output Description

对于每个测试数据，在单独一行内输出最少需要的金币数。

样例输入 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

很容易想到构造一个图，图的各节点就是各个物品，权值就是优惠后的价格 把商人设置为0.，找到1的最短路即可。由于受到等级限制，经过的节点必须和1的等级相差不超过m，那么对于每个上下相差值为m的区间查找最短路即可，最后取最小值。

方便大家理解，画了一张很拙劣的图，大家凑活看一下

![SouthEast][]

代码放上：

//poj1062 codevs1324 °º¹óµÄÆ¸Àñ Ã¶¾Ù+dij
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=0x3f3f3f3f;
    int dis[105],vis[105];
    int lev[105],a[105][105],n,m;
    
    void dij(int l,int r){
    	memset(dis,0x3f,sizeof(dis));
    	memset(vis,0,sizeof(vis));
    	vis[0]=1;dis[0]=0;
    	for (int i=1;i<=n;i++) dis[i]=a[0][i];
    	for (int i=0;i
          
           =l)&&(lev[j]<=r)&&(dis[j])) 
    			  if (dis[j]
           
            =l)&&(lev[j]<=r)&&(a[minj][j])){ int temp=a[minj][j]+dis[minj]; if ((!dis[j])||((dis[j])&&(dis[j]>temp))) dis[j]=temp; } } return; } int main(){ freopen("1.txt","r",stdin); while (scanf("%d%d",&m,&n)==2){//m is status while n is the number of items memset(a,0,sizeof(a)); for (int i=1;i<=n;i++){ int p,l,x; scanf("%d%d%d",&p,&lev[i],&x); a[0][i]=p; for (int j=1;j<=x;j++){ int t,v;//number and discounted price scanf("%d%d",&t,&v); a[t][i]=v; } } lev[0]=lev[1]; int ans=maxn; for (int i=lev[1]-m;i<=lev[1];i++){//here is the problem dij(i,i+m); if (dis[1]

`在这里还要特别说明一下大整数常量的定义  constintmaxn=0x3f3f3f3f; 这真是极好的存在= =引用一下一篇已经消失的博文的解释（顺便吐槽域名重定向去了什么鬼地方）： 0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的， 所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出 （这就满足了“无穷大加一个有穷的数依然是无穷大”）， 事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围， 所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。 最后，0x3f3f3f3f还能给我们带来一个意想不到的额外好处： 如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))这样的代码来实现（方便而高效）， 但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化）， 就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦）， 我们知道这是因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0， 现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！ 所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。 所以在通常的场合下，0x3f3f3f3f真的是一个非常棒的选择。 总结起来就是三句话 1 够大，一般这么大你不会用到 2 够大但不容易溢出 3 方便数组赋值（如果你用FF会变成负数，符号位也会成1） 一轮开始了，该来的总会来的。 欢迎小花加入C党大家族，本科同学你现在是一个人了，摸头···祝小花的喜家家之路一帆风顺。 ——君子博学而日参省乎己，则知明而行无过矣。`

[SouthEast]: /images/20220805/6f2aad07ffae4938ae6a689ed4bda6af.png