POJ 1062 昂贵的聘礼

非常老的题目了,枚举层次dijkstra,G++AC

昂贵的聘礼

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 33747 Accepted: 9652

Description

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

Input

输入第一行是两个整数M,N(1 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

Source

浙江

#include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int maxn=1200; int dist[maxn],g[maxn][maxn],N,M; int level[maxn],within[maxn],value[maxn]; bool vis[maxn]; int dijkstra() { for(int i=1;i=kinglevel-M+i&&level[j]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:UVALive - 3403 Mobile Computing
下一篇:poj 3692 Kindergarten(最大独立点集 + 二分图最大匹配)
相关文章

POJ3621最优比率生成环 01分数规划问题

poj 1928

poj 3728 tarjan+带权路径并查集

poj 3321

POJ 1664 放苹果 递推

poj 1631

poj模拟题总结(一)

POJ 1083

POJ 1952 BUY LOW, BUY LOWER

poj 1195

图文推荐
POJ 1062 昂贵的聘礼
ZOJ 3640 Help Me
POJ 1062 昂贵的聘礼
CF 518C(Anya and
POJ 1062 昂贵的聘礼
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-03 人气:3
本文关键词:
分享到:

相关文章

  • POJ 1062 昂贵的聘礼 最短路 2013-02-07

    Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只要5000金币就行了。"探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接

  • POJ -1062 昂贵的聘礼(前向星 && SPFA) 2014-02-02

    题目链接:昂贵的聘礼 这个题对自己收获挺大的,模板要自己经常敲,才能理解,要自己经常敲,从能温故而知新,自己以前总结的建图方式,做题的时候要会用,要敢用,否则==NULL。 题意对于交换条件描述的有点不清楚,这里解释一下,假设8件物品,等级差距不能超过3,酋长LV 5,所以可以进行交换的LV区间是[2,5][3,6][4,7][5,8],不必考虑题目那一句,“但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样”。越看越晕,只要符合以上区

  • codeforces--Spreadsheets(模拟) 2012-06-09

    Spreadsheets Time Limit:10000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Appoint description: System Crawler (2015-01-06) Description In the popular spreadsheets systems (for example, in Excel) the following numeration of

  • poj1328Radar Installation(贪心-区间选点) 2012-08-22

    题目链接: 啊哈哈,点我点我 题目: Radar Installation Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 52037 Accepted: 11682 Description Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island

  • 使用C++将OpenCV中Mat的数据写入二进制文件,用Matlab读出 2012-09-13

    在使用OpenCV开发程序时,如果想查看矩阵数据,比较费劲,而matlab查看数据很方便,有一种方法,是matlab和c++混合编程,可以用matlab访问c++的内存,可惜我不会这种方式,所以我就把数据写到文件里,用matlab读出来,然后用matlab各种高级功能查看数据的值。 1、将Mat的数据写入指定文件 为了方便拿来主义者,我直接把这个函数贴出来,你只要把代码拷贝到自己的代码里,就可以直接用了。如果有问题,赶紧评论,我会尽快看看问题出在哪里。 #include #include #in

  • UVALive - 3403 Mobile Computing 2013-01-01

    题意:给出房间的宽度r和s个挂钩的重量。设计一个尽量宽,但宽度不超过房间宽度的天平,挂着所有的挂钩。挂钩的宽度不计,且不相同的挂钩可以互相重叠 思路:每次将当前集合分成两个不相交的子集合,每次都构造出子集的最大的天平,最后从子集中选出最大的 #include #include #include #include #include using namespace std; const int MAXN = 65; double r,w[10],value[MAXN],ans; struct nod

  • poj1062 最短路(加限制) 2013-05-09

    http://poj.org/problem?id=1062 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只要5000金币就行了。"探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格

  • POJ 3250 Bad Hair Day(单调栈) 2012-01-07

    题目地址:POJ 3250 初学单调栈。多校和网络赛已经碰到两次了。 单调栈的原理简单的不能再简单了。。就是让栈里的元素从栈顶到栈底呈单调性。 比如说递增单调栈。 每次放进一个数的时候,如果栈顶的数小于要放的数,就把栈顶的数pop出来使得栈里保持单调性。 对于这道题来说,就从右往左开始遍历,建一个递增单调栈。那么每次pop出来的就是当前的牛可以看到的牛数。然后累加即可。 代码如下: #include #include #include #include #include #include #in

  • Curling 2.0 (poj 3009 dfs) 2012-01-10

    Language: Default Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11954 Accepted: 5061 Description On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.044 (s). 10 q(s)