【最短路径】poj 1062

2024-06-14 01:48
文章标签 路径 最短 poj 1062

本文主要是介绍【最短路径】poj 1062,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

昂贵的聘礼
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 36705 Accepted: 10577

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

Source

浙江

题意:就不多说了

思路:最短路问题,dijkstra算法的运用

重难点:

每个物品看成一个节点,酋长的允诺也看作一个物品, 如果一个物品加上金币可以交换另一个物品,
则这两个节点之间有边,权值为金币数,求第一个节点到所有节点的最短路。
因为有等级限制,所以枚举每个点作为最低等级,选取符合所有符合等级限制的点

 

最短路问题,不过因为存在着等级的差异所以需要枚举一下。本题的思路就是对冒险者的等级进行枚举,也就是说冒险者只能和在他等级以上的人进行交易。这样枚举的好处是能够把所有的情况都考虑进去。有一点需要注意:酋长的等级不一定是最高的

 

构图时要注意的是,酉长的承诺不是 最初的源点,它是一个目标点,也就是说点到点的指向方向是由 无替代品的点 逐渐指向到 酉长的承诺1点,题意说明的是一个回溯的过程,因此可以定义一个最初的源点0点,它到其他各点的权值就是每个物品的原价,而点A到点B的权值 就是 物品B在有第A号替代品情况下的优惠价


代码如下:

#include <stdio.h>
#include <string.h>
#define INF 0x7fffffff//无限大int price[110][110],vis[110],d[110],lv[110];//物品i在有第t号替代品情况下的优惠价pricr[t][i],当t=0时说明i无替代品,此时为原价
int dij(int n)
{int i,j,v,mina;for(i=1;i<=n;i++)d[i]=price[0][i];for(i=1;i<=n;i++){v = 0;mina = INF;for(j=1;j<=n;j++){if(!vis[j] && mina>d[j]){mina = d[j];v = j;}}if(v==0)break;vis[v]=1;for(j=1;j<=n;j++){if((!vis[j]) && (price[v][j]!=INF) && (d[j]>d[v]+price[v][j]))///必须要加上(price[v][j]!=INF)这一句否则越界d[j]=d[v]+price[v][j];}}//for(j=1;j<=n;j++)//    printf("%d ",d[i]);return d[1]; //返回当前次交易后目标点1在等级lv[i]约束下的最短距离
}
int main()
{int i,j,k,m,n,num;int t,u,maxlv,temp,minprice=INF;//printf("%d\n",INF);scanf("%d%d",&m,&n);memset(vis,0,sizeof(vis));memset(lv,0,sizeof(lv));for(i=0;i<=n;i++)for(j=0;j<=n;j++)price[i][j]=INF;for(i=0;i<=n;i++)d[i]=INF;for(i=1;i<=n;i++){scanf("%d%d%d",&price[0][i],&lv[i],&num);//price[0][i]物品i无替代品时的原价for(j=1;j<=num;j++){scanf("%d%d",&t,&u);price[t][i]=u;}}minprice = INF;for(i=1;i<=n;i++){maxlv=lv[i];for(j=1;j<=n;j++){if(lv[j]>maxlv || maxlv -lv[j]>m)vis[j]=1;elsevis[j]=0;}temp = dij(n);//printf("%d\n",temp);if(minprice >temp)minprice = temp;}printf("%d\n",minprice);return 0;
}
//AC  C++ 0MS  204K
//<span style="font-size:18px;">dijkstra</span>算法

体会:dijkstra算法的变形使用,多次求dijkstra



这篇关于【最短路径】poj 1062的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059037

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M