广安发展建设集团公司网站,工业品电商平台排行榜,南昌做网站哪家最好,精通网站开发书籍题目 年轻的探险家来到了一个印第安部落里。 在那里他和酋长的女儿相爱了#xff0c;于是便向酋长去求亲。 酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。 探险家拿不出这么多金币#xff0c;便请求酋长降低要求。 酋长说#xff1a;”嗯#xff0c;如果你能够替我…题目 年轻的探险家来到了一个印第安部落里。 在那里他和酋长的女儿相爱了于是便向酋长去求亲。 酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。 探险家拿不出这么多金币便请求酋长降低要求。 酋长说”嗯如果你能够替我弄到大祭司的皮袄我可以只要 8000 金币。如果你能够弄来他的水晶球那么只要 5000 金币就行了。” 探险家就跑到大祭司那里向他要求皮袄或水晶球大祭司要他用金币来换或者替他弄来其他的东西他可以降低价格。 探险家于是又跑到其他地方其他人也提出了类似的要求或者直接用金币换或者找到其他东西就可以降低价格。 不过探险家没必要用多样东西去换一样东西因为不会得到更低的价格。 探险家现在很需要你的帮忙让他用最少的金币娶到自己的心上人。 另外他要告诉你的是在这个部落里等级观念十分森严。 地位差距超过一定限制的两个人之间不会进行任何形式的直接接触包括交易。 他是一个外来人所以可以不受这些限制。 但是如果他和某个地位较低的人进行了交易地位较高的的人不会再和他交易他们认为这样等于是间接接触反过来也一样。 因此你需要在考虑所有的情况以后给他提供一个最好的方案。 为了方便起见我们把所有的物品从 1 开始进行编号酋长的允诺也看作一个物品并且编号总是 1。
每个物品都有对应的价格 P主人的地位等级 L以及一系列的替代品 Ti 和该替代品所对应的”优惠” Vi。
如果两人地位等级差距超过了 M就不能”间接交易”。
你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
输入格式 输入第一行是两个整数 MN依次表示地位等级差距限制和物品的总数。 接下来按照编号从小到大依次给出了 N 个物品的描述。 每个物品的描述开头是三个非负整数 P、L、X依次表示该物品的价格、主人的地位等级和替代品总数。 接下来 X 行每行包括两个整数 T 和 V分别表示替代品的编号和”优惠价格”。
输出格式 输出最少需要的金币数。
数据范围
1 ≤ N ≤ 100 1 ≤ P ≤ 10000 1 ≤ L , M ≤ N 0 ≤ X N
思路
我们可以根据以下样例绘制一张图
样例
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0 由图可知我们可以反向建图从起始点出发到达所有点的距离为物品 i 的原价从点 i 到点 j 的距离为得到物品 i 之后物品 j 的价格。当我们建完图之后很容易发现这个问题可以抽象成为一个最短路问题。 对于阶级问题for(int i level[ 1 ] - m; i level[ 1 ]; i ) res min(res,dijkstra(i, i m)); i 表示可以交换的下界i m表示可以交换的上界 循环m次即可得到最小的花费。 代码
#includebits/stdc.h
using namespace std;
const int N 110,INF 0x3f3f3f3f;
int n,m;// n等级差距限制m物品个数
int w[N][N],level[N];//level数组储存的是第i个物品的主人所处的阶级w数组储存点i到点j的边权
int dist[N];// 表示当前买到第i件物品价格的最小值
bool st[N];// 表示当前物品的价格是否为最小值int dijkstra(int down,int up)
{memset(dist,0x3f,sizeof(dist));// 将价格初始化为正无穷memset(st,0,sizeof(st));// 所有物品都没有确定最小价格dist[0] 0;// 将起始点价格初始化为0int i n;while(i --)// 循环n次确定n个物品的最小价格{int t -1;// 在没有找到下一个可以确定价格已经最低的物品编号之前t -1for(int j 0; j n; j )// 本次循环确定价格最小的物品编号if(!st[j] (t -1 || dist[t] dist[j]))t j;st[t] true;// 该物品已经确定为最小价格标记一下for(int j 1; j n; j )// 使用这个已经确定最小价格的点对其他点进行更新if(level[j] down level[j] up)// 如果阶级不符合条件则不进行更新dist[j] min(dist[j],dist[t] w[t][j]);}return dist[1];
}int main()
{cin m n;// m等级差距限制n物品总数memset(w,0x3f,sizeof(w));// 将数组w初始化for(int i 1;i n; i ) w[i][i] 0;for(int i 1;i n; i ){int price,cnt;// price表示物品的价格cnt表示替代品的数量cin price level[i] cnt;// 依次输入物品的价值物品主人的阶级代替品的数量w[0][i] min(price,w[0][i]);// 起始点到该物品的距离物品原价while(cnt --){int id,cost;cin id cost;// 输入替代品的数量与价格w[id][i] min(w[id][i],cost);//保留边权最小的值}}int res INF;// 将答案初始化为正无穷for(int i level[1] - m; i level[1]; i ) res min(res,dijkstra(i, i m));// i表示可以交换的下界i m表示可以交换的上界cout res endl;return 0;}
