昂贵的聘礼
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 34167 | Accepted: 9767 |
Description
年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只要5000金币就行了。"探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。另外他要告诉你的是,在这个部落里,等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。他是一个外来人,所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见,我们把所有的物品从1开始进行编号,酋长的允诺也看作一个物品,并且编号总是1。每个物品都有对应的价格P,主人的地位等级L,以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M,就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
为了方便起见,我们把所有的物品从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
题意:
给出M,N(1 ~ 100),代表等级差距M和有N个物品。后给出这N个物品的信息,每个信息首先给出3个数,分别代表该物品的价格,等级和可替代品的数量K,后给出 K 个物品,每个物品给出两个数,代表该物品的编号和优惠价格。优惠价格表示,若你拥有该替换物品,那么就只需要花费优惠价格的价钱就能获得该物品,而不需要支付本身这个物品价格的价钱。问如果购买,使要获得第一个物品所支付的价钱最少。还有一个限制条件就是,购买物品交换期间任何两样物品间的等级差距不能超过 M 。
思路:
最短路。Dijkstra + 邻接表 + 优先队列 + 枚举区间。对于要首先取哪件物品作为购买起点是不确定的,所以对于每一个除了1号物品之外都要进行一次最短路来确定最小值。除此之外,因为有等级的限制,所以会要通过重点和起点两个物品的等级来确定等级区间,比如起点等级是3,终点等级是4,不能超过的登记是3,故总共可能的区间可能是 1 ~ 4,2 ~ 5,3 ~ 6 这三个区间,所以对于每个区间都要最短路一次。所以对于每个起点都有枚举期间来进行最短路。最后比较最小值即可。
AC:
#include <cstdio> #include <iostream> #include <queue> #include <vector> #include <utility> #include <string.h> #include <algorithm> #define MAX 5000 #define INF 99999999 using namespace std; typedef pair<int,int> pii; typedef struct { int mon; int ran; }node; node no[105]; int v[MAX],fir[105],next[MAX],w[MAX]; int d[105],vis[105]; int ind,n,m; void add_edge(int f,int t,int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ind++; } int Dijkstra(int num,int mon,int min_r,int max_r) { memset(vis,0,sizeof(vis)); for(int i = 1;i <= n;i++) d[i] = INF; d[num] = mon; priority_queue<pii,vector<pii>,greater<pii> > q; q.push(make_pair(d[num],num)); while(!q.empty()) { pii t = q.top();q.pop(); int x = t.second; if(vis[x]) continue; vis[x] = 1; for(int e = fir[x];e != -1;e = next[e]) { int y = v[e]; if(min_r <= no[y].ran && max_r >= no[y].ran && d[y] > d[x] + w[e]) { d[y] = d[x] + w[e]; q.push(make_pair(d[y],y)); } } } return d[1]; } int main() { ind = 0; memset(fir,-1,sizeof(fir)); scanf("%d%d",&m,&n); for(int i = 1;i <= n;i++) { int num; scanf("%d%d%d",&no[i].mon,&no[i].ran,&num); while(num--) { int ans,mon; scanf("%d%d",&ans,&mon); add_edge(ans,i,mon); } } int min_mon = INF; for(int i = 2;i <= n;i++) { int min_r = min(no[i].ran,no[1].ran); int max_r = max(no[i].ran,no[1].ran); if(max_r - min_r > m) continue; int ans,from; from = max_r - m < 0 ? 1 : max_r - m; for(from;from <= min_r;from++) { ans = Dijkstra(i,no[i].mon,from,from + m); if(ans < min_mon) min_mon = ans; } } if(min_mon == INF) printf("%d\n",no[1].mon); else printf("%d\n",min_mon); return 0; }
相关推荐
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python...
Dijkstra算法C++邻接表实现,用邻接表存图,还有记录路径。
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip主要针对计算机相关专业的正在做课程设计和期末大作业的学生和需要项目实战练习的学习者。包含全部项目源码、该项目可以直接使用、项目都经过...
用堆优化的dijkstra,接口为邻接链表。
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
用邻接表表示的数据结构,及DIJKSTRA算法实现的最短路径程序
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
1、基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip 2、该资源包括项目的全部源码,下载可以直接使用! 3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...
Dijkstra算法求最短路,利用C++程序设计,希望能对你有所帮助
dijkstra算法,最短路问题Dijkstra算法,网络无负权的最短问题Dijkstra算法
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...
标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
abcde
最短路Dijkstra算法 Matlab代码Function部分,通用各种类型网络
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码+项目使用说明.zip 语言:Python 主要依赖包: PyQt5 主要算法: Dijkstra 通过工程文件 - > 在配置好的IDE中运行 main.py - > 或cd 进入工程目录 python -...
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
文档最短路问题Dijkstra算法提取方式是百度网盘分享地址
【老生谈算法】floyd最短路算法Dijkstra最短路算法Matlab程序.doc