POJ1062:昂贵的聘礼(dfs)
昂贵的聘礼
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 58108 | Accepted: 17536 |
题目链接:http://poj.org/problem?id=1062
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
题解:
其实这题可以枚举+最短路来做的,由于我太菜了,写了个搜索水过去了。。其余不多说吧....
代码如下:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = ,t = ;
int m,n;
vector <int> vec[N],pri[N];
int l[N],head[N],vis[N];
struct Edge{
int u,v,w,next;
}e[N*N<<];
int tot;
void adde(int u,int v,int w){
e[tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;
}
int ans=INF;
void dfs(int u,int mx,int mn,int sum){
vis[u]=;
if(u==t){
ans=min(ans,sum);
return ;
}
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(vis[v]) continue ;
if((abs(l[v]-mn)>m || abs(l[v]-mx)>m) &&v!=t) continue ;
dfs(v,max(l[v],mx),min(l[v],mn),sum+e[i].w);
vis[v]=;
}
}
int main(){
scanf("%d%d",&m,&n);
memset(head,-,sizeof(head));
for(int i=;i<=n;i++){
int p,x;
scanf("%d%d%d",&p,&l[i],&x);
adde(i,t,p);
for(int j=,tmp;j<=x;j++){
scanf("%d%d",&tmp,&p);
adde(i,tmp,p);
}
}
dfs(,l[],l[],);
cout<<ans;
return ;
}
最新文章
- sizzle分析记录:getAttribute和getAttributeNode
- 【2016-10-31】【坚持学习】【Day16】【MongoDB】【入门】
- 七牛CEO许式伟:移动游戏资源存贮的大趋势
- 统计Codec RAM和ROM方法
- SqlDataReader、SqlDataAdapter與SqlCommand的 区别
- /boot/grub/menu.lst详解
- 【疯狂Java学习笔记】【第一章:Java语言概述】
- <;转>;MySQL性能优化的最佳20+条经验
- 20160504-hibernate入门
- android 补间动画
- Java 基础类型
- MFC属性表单修改“应用”键名并对其响应
- Android 网络图片加载之cude 框架
- vim命令替换操作
- ECMA Script 6_必须要知道的基础
- R语言读取JSON数据
- KillerBee
- CSS3实战开发: 折角效果实战开发
- onclick 常用手册
- 转载一篇介绍CUDA
热门文章
- R语言学习笔记(十):零碎知识点(21-25)
- 10 TCP 传输控制协议 UDP区别
- 1698-Just a Hook 线段树(区间替换)
- LeetCode:14. Longest Commen Prefix(Easy)
- 关于实现mybatis order by 排序传递参数实现 问题记录
- 使用Entity Framework时,序列化出错
- java设计模式大全 Design pattern samples in Java(最经典最全的资料)
- VS2013生产过程问题及解决
- npm命令 VS yarn命令
- python 基础篇 04(列表 元组 常规操作)