蓝桥杯练习系统(算法训练)ALGO-954 逗志芃的暴走

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  逗志芃是有妹子的现充,但是有时候妹子就是烦恼。因为逗志芃太逗了,所以这段时间妹子对逗志芃发动了技能无理取闹,妹子要去玩很多的景点。由于逗志芃之前抽机花费了太多的时间,不久以后又要微积分考试了,所以现在被妹子搞成暴走状态了。但是妹子永远是上帝,所以逗志芃只能带妹子出去玩,不过为了节约时间,他希望找到一条花费时间最少的一次性游览线路。

输入格式

  第一行1个数n,表示逗志芃所在的城市有多少个景点,接下来是一个n*n的矩阵。a(i,j)表示i号景点到j号景点的路上花费的时间是多少。
  接下来是一个数m,表示逗志芃妹子要去去的景点数目。由于妹子在无理取闹,所以可能会有重复的景点,不过只要去一次就可以了。接下来是m个数,就是妹子要去的景点编号。

输出格式

  一个数,最少的花费时间。

样例输入

3
0 1 2
1 0 3
2 3 0
3
2 3 1

样例输出

3

数据规模和约定

  0<n<=30,0<m<=20,时间<=1000000

#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
const int N=35;
int mp[N][N];
int visit[N];//妹妹要去的景点
bool vis[N];//已访问的景点 
int ans=0x3f3f3f3f;
int cnt=0;//实际的景点数
int n;//n个点
//深度遍历求游览计划的最短时间 
void dfs(int pos,int count,int sum){//pos为当前的景点,count为已访问的景点数,sum为时间 if(count==cnt){ans=min(ans,sum);return;}for(int i=1;i<=n;i++){if(visit[i]&&!vis[i]&&sum<ans){vis[i]=true;mp[0][i]=0;dfs(i,count+1,sum+mp[pos][i]);vis[i]=false;}}
} 
int main(){ cin>>n;memset(mp,0x3f,sizeof(mp));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j]; }} int m;//要去的景点数 cin>>m;for(int i=1;i<=m;i++){int x;cin>>x;if(visit[x]==0) cnt++;visit[x]=1;} for(int k=1;k<=n;k++){//通过点k中转 for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&i!=k&&k!=j&&mp[i][j]>mp[i][k]+mp[k][j]){mp[i][j]=mp[i][k]+mp[k][j];}}} }dfs(0,0,0);cout<<ans<<endl;return 0;
}

思路:先使用Floyed算法求每个点之间的最短时间,然后用dfs将访问景点的顺序进行全排列(即遍历每一种情况) 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/308271.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Vue + keep-alive】路由缓存

一. 需求 列表页&#xff0c;n 条数据项可打开 n 个标签页&#xff0c;同时1条数据项的查看和编辑共用一个标签页。如下所示&#xff1a; 参考 // 主页面 // 解决因 路由缓存&#xff0c;导致 编辑后跳转到该页面 不能实时更新数据 onActivated(() > {getList() })二. 实现…

JAVA 4

这次我学习了第四次Java课程 Math #include<math.h> 数学运算 Math.main 随机数 double aMath.random(); System.out.println(a);对小数处理 double a 3.6415; System.out.println("Math.floor: " Math.floor(a));//向下最近的整数 System.out.println(&…

wpf下如何实现超低延迟的RTMP或RTSP播放

技术背景 我们在做Windows平台RTMP和RTSP播放模块对接的时候&#xff0c;有开发者需要在wpf下调用&#xff0c;如果要在wpf下使用&#xff0c;只需要参考C#的对接demo即可&#xff0c;唯一不同的是&#xff0c;视频流数据显示的话&#xff0c;要么通过控件模式&#xff0c;要么…

【黑马头条】-day09用户行为-精度丢失-点赞收藏关注

文章目录 1 long类型精度丢失问题1.1 解决1.2 导入jackson序列化工具1.3 自定义注解1.4 原理1.5 测试 2 用户行为要求3 创建微服务behavior3.1 微服务创建3.2 添加启动类3.3 创建bootstrap.yml3.4 在nacos中配置redis3.5 引入redis依赖3.6 更新minio 4 跳过 1 long类型精度丢失…

小红的白色字符串

题目描述 小红拿到了一个字符串&#xff0c;她准备将一些字母变成白色&#xff0c;变成白色的字母看上去就和空格一样&#xff0c;这样字符串就变成了一些单词。 现在小红希望&#xff0c;每个单词都满足以下两种情况中的一种&#xff1a; 1.开头第一个大写&#xff0c;其余为…

01、ArcGIS For JavaScript 4.29对3DTiles数据的支持

综述 Cesium从1.99版本开始支持I3S服务的加载&#xff0c;到目前位置&#xff0c;已经支持I3S的倾斜模型、3D Object模型以及属性查询的支持。Cesium1.115又对I3S标准的Building数据实现了加载支持。而ArcGIS之前一直没有跨越对3DTiles数据的支持&#xff0c;所以在一些开发过…

抖音滑块验证码加密的盐的位置

最近更新后之前很容易找到盐的位置的方法变了&#xff0c;抖音特意把盐隐藏起来了 {"reply": "RJC","models": "yAd8rl","in_modal": "DTn0nD2","in_slide": "ou7H0Ngda","move": …

Vue2(十五):replace属性、编程式路由导航、缓存路由组件、路由组件独有钩子、路由守卫、history与hash

一、router-link的replace属性 1、作用&#xff1a;控制路由跳转时操作浏览器历史记录的模式 2、浏览器的历史记录有两种写入方式&#xff1a;分别为push和replace&#xff0c;push是追加历史记录&#xff0c;replace是替换当前记录。路由跳转时候默认为push 3、如何开启repla…

环信 IM 客户端将适配鸿蒙 HarmonyOS

自华为推出了自主研发操作系统鸿蒙 HarmonyOS 后&#xff0c;国内许多应用软件开始陆续全面兼容和接入鸿蒙操作系统。环信 IM 客户端计划将全面适配统鸿蒙 HarmonyOS &#xff0c;助力开发者快速实现社交娱乐、语聊房、在线教育、智能硬件、社交电商、在线金融、线上医疗等广泛…

基于java+springboot+vue实现的网上购物系统(文末源码+Lw+ppt)23-42

摘 要 随着我国经济的高速发展与人们生活水平的日益提高&#xff0c;人们对生活质量的追求也多种多样。尤其在人们生活节奏不断加快的当下&#xff0c;人们更趋向于足不出户解决生活上的问题&#xff0c;网上购物系统展现了其蓬勃生命力和广阔的前景。与此同时&#xff0c;为…

我与C++的爱恋:类与对象(二)

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;我与C的爱恋 ​ 本篇着重介绍构造函数和析构函数&#xff0c;剩余内容在下篇解答。 一、类的默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 任何类在什么都不写时…

GFS部署实验

目录 1、部署环境 ​编辑 2、更改节点名称 3、准备环境 4、磁盘分区&#xff0c;并挂载 5. 做主机映射--/etc/hosts/ 6. 复制脚本文件 7. 执行脚本完成分区 8. 安装客户端软件 1. 安装解压源包 2. 创建gfs 3. 安装 gfs 4. 开启服务 9、 添加节点到存储信任池中 1…

RUM 最佳实践-交互延迟的探索与发现

FID 在互联网高速发展的时代&#xff0c;用户体验已成为企业竞争的关键所在。网页性能作为用户体验的重要组成部分&#xff0c;直接影响着用户的满意度和工作效率。First Input Delay&#xff08;FID&#xff09;作为衡量网页性能的重要指标&#xff0c;越来越受到业界关注。今…

【Linux学习笔记】安卓运行C可执行文件No such file or directory

文章目录 开发环境运行失败现象解决办法方法一&#xff1a;使用静态库方法二&#xff1a;使用动态库创建lib查找依赖库复制需要注意的事情 开发环境 开发板&#xff1a;正点原子RK3568开发板安卓版本&#xff1a;11可执行程序命名&#xff1a;ledApp需加载模块&#xff1a;dts…

SpringBoot3 + uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作(最新)

SpringBoot3 uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作 最终效果图uniapp 的源码UpLoadFile.vuedeleteOssFile.jshttp.js SpringBoot3 的源码FileUploadController.javaAliOssUtil.java 最终效果图 uniapp 的源码 UpLoadFile.vue <tem…

云服务器环境web环境搭建之JDK、redis、mysql

一、Linux安装jdk&#xff0c;手动配置环境 链接: https://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1whttps://pan.baidu.com/s/1LRgRC5ih7B9fkc588uEQ1w 提取码: 0413 tar -xvf 压缩包名 修改配置文件/etc/profile 二、安装redis环境 方案一&#xff1a; Linux下安装配置r…

clickhouse深入浅出

基础知识原理 极致压缩率 极速查询性能 列式数据库管理 &#xff0c;读请求多 大批次更新或无更新 读很多但用很少 大量的列 列的值小数值/短字符串 一致性要求低 DBMS&#xff1a;动态创建/修改/删除库 表 视图&#xff0c;动态查/增/修/删&#xff0c;用户粒度设库…

数据治理专家岗位的能力模型

数据治理专家的角色要求其具备全方位的专业素养与技能&#xff0c;不仅要有深厚的业务理解与数据技术功底&#xff0c;还需展现出卓越的领导力、团队协作与沟通能力&#xff0c;以驱动组织内部数据治理工作的高效运行与持续优化。以下是对数据治理专家各项能力的深入解读&#…

mac 配置前端开发环境brew,git,nvm,nrm

我的电脑是mac 3 pro 一、配置Homebrew 打开终端&#xff0c;执行指令 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"查看版本 brew -v 安装nvm brew install nvm 再执行 brew reinstall nvm 我这边安装好了…

JavaScript中的Blob、Buffer、ArrayBuffer和TypedArray详解

文章的更新路线&#xff1a;JavaScript基础知识-Vue2基础知识-Vue3基础知识-TypeScript基础知识-网络基础知识-浏览器基础知识-项目优化知识-项目实战经验-前端温习题&#xff08;HTML基础知识和CSS基础知识已经更新完毕&#xff09; 正文 摘要&#xff1a;本文详细介绍了JavaS…