AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维
我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。
#include <iostream>
using namespace std;
int inf = 0x3f3f3f3f, num[1007], dp[1007][207], L[207][207], S[207][207], N, M, R;
void init()
{for (int i = 1; i <= N; i++){for (int j = 1; j <= N; j++){L[i][j] = inf;S[i][j] = inf;}L[i][i] = 0;S[i][i] = 0;}
}
void input()
{int from, to, cost;char op;for (int i = 1; i <= M; i++){scanf("%d %d %d %c\n", &from, &to, &cost, &op);if (op == 'S'){if (cost < S[from][to]){S[from][to] = cost;}if (cost < S[to][from]){S[to][from] = cost;}}else if (op == 'L'){if (cost < L[from][to]){L[from][to] = cost;}if (cost < L[to][from]){L[to][from] = cost;}}}scanf("%d", &R);for (int i = 1; i <= R; i++){scanf("%d", &num[i]);}
}
void floyd()
{for (int k = 1; k <= N; k++){for (int i = 1; i <= N; i++){for (int j = 1; j <= N; j++){if (L[i][k] != inf && L[k][j] != inf){if (L[i][k] + L[k][j] < L[i][j]){L[i][j] = L[i][k] + L[k][j];}}if (S[i][k] != inf && S[k][j] != inf){if (S[i][k] + S[k][j] < S[i][j]){S[i][j] = S[i][k] + S[k][j];}}}}}
}
void handleNormalLine(int i, int j)
{// dp[i][j]是从num[1]到达num[i],并且到达num[i]时船在j的最小路径,当i大于1时,dp[i][j]一定与num[i-2]走到num[i-1]时停船的位置有关// 我们需要从num[i-1]走陆路到k,然后走水路到j,把船停在j,之后走陆路从j到num[i]dp[i][j] = inf;for (int k = 1; k <= N; k++){if (k != j){// 从num[i-1]到k的陆路不通,从k到j的水路不通,从j到num[i]的陆路不通,从1到num[i-1]并且停船到k实现不了,那么这种情况不用计算if (L[num[i - 1]][k] == inf || S[k][j] == inf || L[j][num[i]] == inf || dp[i - 1][k] == inf){continue;}if (L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k] < dp[i][j]){dp[i][j] = L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k];}}else{// k和j相等时,就不需要走陆路到k,然后再走水路到j了,直接从num[i-1]走陆路到num[i]即可,因为j==k船已经在j了,不用管船if (L[num[i - 1]][num[i]] == inf || dp[i - 1][k] == inf){continue;}if (L[num[i - 1]][num[i]] + dp[i - 1][k] < dp[i][j]){dp[i][j] = L[num[i - 1]][num[i]] + dp[i - 1][k];}}}
}
void handleFirstLine(int i, int j)
{// i=1时,船就在num[i],dp[i][j] i=1 代表开船到j,船放在j,然后陆路走回来num[i]// 走水路开船从num[i]到j,然后船停在j,之后从j走陆路回到num[i],如果num[i]到j的水路,或者j到num[i]的陆路不通,那么这个都无法实现if (S[num[i]][j] == inf || L[j][num[i]] == inf){dp[i][j] = inf;return;}dp[i][j] = S[num[i]][j] + L[j][num[i]];
}
void doDp()
{// 我们用dp[i][j] 代表邮递员从 num[1]按照顺序一个个走到num[i],即达到邮递员在num[i]且船的位置在j的状态下,最小的消耗for (int i = 1; i <= R; i++){for (int j = 1; j <= N; j++){if (i == 1){handleFirstLine(i, j);}else{handleNormalLine(i, j);}}}
}
int findAns()
{int ans = inf;for (int i = 1; i <= N; i++){if (dp[R][i] < ans){ans = dp[R][i];}}return ans;
}
int main()
{while (true){scanf("%d%d", &N, &M);if (N == 0 && M == 0){break;}init();input();floyd();doDp();printf("%d\n", findAns());}return 0;
}
相关文章:
AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维
我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。 #include <iostream> using namespace std; int inf 0x3f3f3f3f, num[1007], dp[1007…...
红米电视 ADB 安装 app 报错 failed to authenticate xxx:5555
开启电视开发者模式,允许安装未知来源应用及开启 ADB 调试电脑端下载 adb 工具 点击下载同一局域网的电脑使用 adb 工具连接(提前查看电视 IP)D:\adb>adb connect 192.168.1.7 * daemon not running; starting now at tcp:5037 * daemon s…...
Linux 下设置开机自启动的方法
文章目录 事先准备对于普通的 Linux对于 RedHat Enterprise Linux 9 笔者的运行环境: 设置成功过的 Linux: RedHat Enterprise Linux 9 x86_64 CentOS 8 x86_64 事先准备 进行这个教程之前,必须要先安装好一个 Linux 操作系统。这个 Linux…...
MySQL常见问题处理(三)
MySQL 常见问题解决 夕阳留恋的不是黄昏,而是朝阳 上一章简单介绍了MySQL数据库安装(二), 如果没有看过, 请观看上一章 一. root 用户密码忘记,进行重置操作 复制内容来源链接: https://blog.csdn.net/weixin_48927364/article/details/123556927 一.…...
maven中常见问题
文章目录 一、配置项提示二、父子打包三、打包之后不显示target四、自定义打包之后的jar包名称五、整个项目打包5.1、父项目管理插件和微服务打包 一、配置项提示 SpringBoot中提示错误信息 表示的是SpringBoot中的注释提示没有配置!那么可以来使用一下springboot官…...
vue2中bus的使用
说明:为了解决组件间的通信,也就是组件与组件间的数据传递(它们之间毫无关系); 这里以组件1传递数据到组件2为例 1.首先新建一个Bus.js文件 import Vue from vue const Bus new Vue() export default Bus 2.在组件1中引用 传递数据 imp…...
实证研究在机器学习中的应用
实证研究是一种基于实际数据和事实的科学研究方法,目的是通过观察、测量、分析和解释数据来验证或否定某个假设、理论或研究问题。这种研究方法通常用于社会科学、自然科学和医学等领域。以下是实证研究的详细解释: 研究目标:实证研究旨在通过…...
IO进程线程day8(2023.8.6)
一、Xmind整理: 管道的原理: 有名管道的特点: 信号的原理: 二、课上练习: 练习1:pipe 功能:创建一个无名管道,同时打开无名管道的读写端 原型: #include <unist…...
【5G NR】逻辑信道、传输信道和物理信道的映射关系
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…...
tmux基础教程
tmux基础教程 Mac安装 brew install tmuxubuntu安装 sudo apt-get install tmux入门使用 会话 (Session) Ctrlb d: 分离当前会话。Ctrlb s: 列出所有会话。Ctrlb $: 重命名当前会话。 窗口(Window) Ctrlb c: 创建一个新窗口, 状态栏会显示多个窗…...
项目实战 — 消息队列(4){消息持久化}
目录 一、消息存储格式设计 🍅 1、queue_data.txt:保存消息的内容 🍅 2、queue_stat.txt:保存消息的统计信息 二、消息序列化 三、自定义异常类 四、创建MessageFileManger类 🍅 1、约定消息文件所在的目录和文件名…...
AI编程工具Copilot与Codeium的实测对比
csdn原创谢绝转载 简介 现在没有AI编程工具,效率会打一个折扣,如果还没有,赶紧装起来. GitHub Copilot是OpenAi与github等共同开发的的AI辅助编程工具,基于ChatGPT驱动,功能强大,这个没人怀疑…...
webpack基础知识六:说说webpack的热更新是如何做到的?原理是什么?
一、是什么 HMR全称 Hot Module Replacement,可以理解为模块热替换,指在应用程序运行过程中,替换、添加、删除模块,而无需重新刷新整个应用 例如,我们在应用运行过程中修改了某个模块,通过自动刷新会导致…...
Linux从安装到实战 常用命令 Bash常用功能 用户和组管理
1.0初识Linux 1.1虚拟机介绍 1.2VMware Workstation虚拟化软件 下载CentOS; 1.3远程链接Linux系统 &FinalShell 链接finalshell半天没连接进去 他说ip adress 看IP地址是在虚拟机上 win11主机是 终端输入: ifconfig VMware虚拟机的设置 & ssh连接_snge…...
webpack基础知识三:说说webpack中常见的Loader?解决了什么问题?
一、是什么 loader 用于对模块的"源代码"进行转换,在 import 或"加载"模块时预处理文件 webpack做的事情,仅仅是分析出各种模块的依赖关系,然后形成资源列表,最终打包生成到指定的文件中。如下图所示&#…...
深度学习:Pytorch常见损失函数Loss简介
深度学习:Pytorch常见损失函数Loss简介 L1 LossMSE LossSmoothL1 LossCrossEntropy LossFocal Loss 此篇博客主要对深度学习中常用的损失函数进行介绍,并结合Pytorch的函数进行分析,讲解其用法。 L1 Loss L1 Loss计算预测值和真值的平均绝对…...
【Android-java】Parcelable 是什么?
Parcelable 是 Android 中的一个接口,用于实现将对象序列化为字节流的功能,以便在不同组件之间传递。与 Java 的 Serializable 接口不同,Parcelable 的性能更高,适用于 Android 平台。 要实现 Parcelable 接口,我们需…...
Spring整合MyBatis小实例(转账功能)
实现步骤 一,引入依赖 <!--仓库--><repositories><!--spring里程碑版本的仓库--><repository><id>repository.spring.milestone</id><name>Spring Milestone Repository</name><url>https://repo.spring.i…...
List集合的对象传输的两种方式
说明:在一些特定的情况,我们需要把对象中的List集合属性存入到数据库中,之后把该字段取出来转为List集合的对象使用(如下图) 自定义对象 public class User implements Serializable {/*** ID*/private Integer id;/*…...
海外媒体发稿:软文写作方法方式?一篇好的软文理应合理规划?
不同种类的软文会有不同的方式,下面小编就来来给大家分析一下: 方法一、要选定文章的突破点: 所说突破点就是这篇文章文章软文理应以什么样的视角、什么样的见解、什么样的语言设计理念、如何文章文章的标题来写。不同种类的传播效果&#…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
