TYVJ 1288 飘飘乎居士取能量块
2024-09-04 14:58:22
背景
9月21日,pink生日;9月22日,lina生日;9月23日,轮到到飘飘乎居士(狂欢吧,(^__^) 嘻嘻……)。
描述
9月21日,今天是pink的生日,飘飘乎居士当然要去别人的领土大闹一番啦!
为了收集更多的能量到pink家大闹,飘飘乎居士准备从后花园中取出自己多年积攒的p个能量块。后花园一共被划分n个地区,能量块被分散在里面,现在飘飘乎居士拿出地图,发现自己站在1的地方,而他要做的就是用最短的路程把所有的能量块取出,并且最后走到位于n的出口处,而飘飘乎居士一直是个懒人,他想知道最少要走多少路程才能够取到所有的能量块,并且走到出口
输入格式
第一行一个正整数n,表示花园被划分成了n个地区
接下来一个n*n的矩阵,代表个点之间的相互距离,数据保证从i走到i没有路程
在下来一个整数p,表示一共有p个能量块
接下来一行,表示各个能量块的位置,数据保证1和n没有能量块,且每个地区最多一个能量块
对于所有的数据 0< n<=100 0<=P<=10 任意两点的距离为一个小于1000的正整数
输出格式
一个数,飘飘乎居士所要行走的最小距离
测试样例1
输入
3
0 10 1
3 0 5
1 2 0
1
2
输出
7
备注
花园被分为3个地区,在2号地区有能量块,飘飘乎居士行走的路线如下
1->3->2->1->3
行走的总路程为7,也就是最后的答案。
思路:
(感谢lyd学长的幻灯片)
//By: Sirius_Ren
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[105][105],b[105],n,p,minn=0x3fffffff;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d ",&a[i][j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
scanf("%d",&p);
for(int i=1;i<=p;i++)scanf("%d",&b[i]);
sort(b+1,b+p+1);b[0]=1;b[p+1]=n;
do{
int sum=0;
for(int i=1;i<=p+1;i++)sum+=a[b[i-1]][b[i]];
minn=min(minn,sum);
}while(next_permutation(b+1,b+p+1));
printf("%d",minn);
}
最新文章
- ae arcgis engine 关于面转线的方法和注意事项
- CF733D Kostya the Sculptor[贪心 排序]
- H5canvas赛车游戏-基于lufylegend引擎
- Android控件之AutoCompleteTextView(自动匹配输入的内容)
- JDK个目录,以及与环境变量的关系
- Windows Phone开发工具初体验【转载】
- Unity3d不支持vistual studio2012?用vs2012打开unity c#脚本进行编码的方法。
- D3画图学习一
- File类的使用
- 使用GDI+绘制的360风格按钮控件(使用CN_DRAWITEM消息重绘,并使用TGPGraphics,TGPPen,TGPImage,TGPBitmap等)good
- 他的第一个NDK的Demo
- C#版(击败100.00%的提交) - Leetcode 372. 超级次方 - 题解
- 怎么解决syntaxerror:non-utf-8 code starting with \xc4&#39;in file
- EasyGui的一个小例子
- Android Vector曲折的兼容之路
- CSS精简工具——除去多余的css样式
- 微信小程序之----获取设备信息
- mapreduce 中 map数量与文件大小的关系
- [AWS] Amazon Cognito
- Spring MVC中使用errors标签
热门文章
- do{}while(0)
- Python 字符串和数字
- Flask - WTF和WTForms创建表单
- C#关键字详解第二节
- 01派【北京大学ACM/ICPC竞赛训练暑期课】
- Django——11 状态保持 form表单 登陆注册样例
- BNUOJ 3958 MAX Average Problem
- (41)Spring Boot 使用Java代码创建Bean并注册到Spring中【从零开始学Spring Boot】
- [JLOI2015]战争调度
- [bzoj4636]蒟蒻的数列_线段树