洛谷——P1690 贪婪的Copy
2024-10-21 16:15:06
P1690 贪婪的Copy
题目描述
Copy从卢牛那里听说在一片叫yz的神的领域埋藏着不少宝藏,于是Copy来到了这个被划分为个区域的神地。卢牛告诉了Copy这里共有个宝藏,分别放在第Pi个(1<=Pi<=N)区域。Copy还得知了每个区域之间的距离。现在Copy从1号区域出发,要获得所有的宝藏并到n号区域离开。Copy很懒,只好来找你为他寻找一条合适的线路,使得他走过的距离最短。
输入输出格式
输入格式:
第一行一个正整数N(1<=N<=100)
接下来一个N*N的矩阵,第i+1行第j列的数字表示区域i,j之间的距离。每个距离用空格隔开,距离保证i,j<=1000。请注意的i to j距离并不一定等于j to i的距离。
第N+2行一个整数P(0<=P<=10)。
第N+3行共P个用空格隔开的整数,表示有宝藏的区域编号。
输出格式:
一个整数,为Copy获得全部宝藏需要的最短距离。数据保证答案小于等于maxlongint。
输入输出样例
输入样例#1:
样例输入1 2 0 4 5 0 2 1 2 样例输入2 3 0 2 6 1 0 4 7 10 0 1 2
输出样例#1:
样例输出1 4 样例输出1 6
说明
对30%的数据,1<=n<=15,其余如题所述。
对100%的数据,全部数据范围如题所述。
由于数据比较小,并且我们要知道每两个点之间的最短路,这样我们就跑一遍Floyd,处理出每一对点之间的最小值。
然后在枚举路径进行更新ans,这个时候我们就可以用next_permutation来枚举这个路径,路径上的点我们是已经知道的,我们可以对这些点的位置进行全排列,这样我们就可以得到所有的路径情况,然后在里面我们用一个pre数组记录上一个步我们走到哪个地方,然后路径的长度+dis[pre][a[i]]最后不要忘记我们最后还要到达n这个点,然后我们再把最后一个点到n的距离加上,更新最小值就好了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1100 using namespace std; int n,m,tmp,sum,ans,pre,dis[N][N],a[N]; int read() { ,f=; char ch=getchar(); ') ch=getchar(); +ch-',ch=getchar(); return x*f; } int main() { n=read(); ;i<=n;i++) ;j<=n;j++) dis[i][j]=read(); m=read(); ;i<=m;i++) a[i]=read(); ;k<=n;k++) ;i<=n;i++) ;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); ans=0x3f3f3f3f; sort(a+,a++m); do { pre=,sum=; ;i<=m;i++) sum+=dis[pre][a[i]],pre=a[i]; sum+=dis[pre][n]; ans=min(ans,sum); },a++m)); printf("%d",ans); ; }
最新文章
- 分布式的Id生成器
- PHP常用代码汇总
- Nginx中文域名配置
- Objective-C 命名规范
- Mac Pro 开机自启动 PHP-FPM,Nginx,MySql 等软件
- Windows环境变量
- node中的流程控制中,co,thunkify为什么return callback()可以做到流程控制?
- Shell中特殊的变量
- qemu/kvm/qemu-kvm/virsh的区别
- mac 下搭建 Android 开发环境
- Eclipse shift + ctrl + F 不好用
- log4cxx入门第一篇--一个小例子
- C# 类型转换is和as 以及性能陷阱
- node 全局对象global —— 记录在线人员
- 【IDEA填坑】xml不编译
- Paper | 学习多任务中的最佳分/ 合结构(十字绣结构)
- angular笔记_5(全选/反选)
- Nginx – rewrite 配置 URL重写及301跳转原理图
- 专业方向系列-00-Python与有限元初探
- 初征——NOIP2018游记