【C++动态规划 图论】3243. 新增道路查询后的最短距离 I|1567

本文涉及知识点

打开打包代码的方法兼述单元测试
C++动态规划
C++图论

LeetCode3243. 新增道路查询后的最短距离 I

给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市,编号从 0 到 n - 1。初始时,每个城市 i 都有一条单向道路通往城市 i + 1( 0 <= i < n - 1)。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后,你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer,对于范围 [0, queries.length - 1] 中的每个 i,answer[i] 是处理完前 i + 1 个查询后,从城市 0 到城市 n - 1 的最短路径的长度。
示例 1:
输入: n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出: [3, 2, 1]
解释:
在这里插入图片描述新增一条从 2 到 4 的道路后,从 0 到 4 的最短路径长度为 3。
在这里插入图片描述
新增一条从 0 到 2 的道路后,从 0 到 4 的最短路径长度为 2。
在这里插入图片描述
新增一条从 0 到 4 的道路后,从 0 到 4 的最短路径长度为 1。
示例 2:
输入: n = 4, queries = [[0, 3], [0, 2]]
输出: [1, 1]
解释:
新增一条从 0 到 3 的道路后,从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后,从 0 到 3 的最短路径长度仍为 1。
提示:
3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。

图论 最短路

注意: 无论是初始路线,还是新增加的路线,都是终点>起点。 → \rightarrow 经过的城市一定是升序。

动态规划的状态表示

dp[i]表示到达i的最少路径。空间复杂度:O(n)

动态规划的填表顺序

令新增加的边是i1->i2。
则 i = i2 ; i > N; i++

动态规划的转移方程

MinSelf(dp[i2],dp[i1]+1)
for(next in neiBo[i])
MinSelf(dp[next],dp[i]+1)
新增一条的时间复杂度:O(m),m是边数,本题是n+q。
总时间复杂度:O(q(n+q))

动态规划的初始化

dp[0]=0,其它INT_MAX/2。
先计算初始各边,再增加查询各边。
增加完边后,刷新dp[i…]封装成函数。也可以进一步简化,更新整个dp。

动态规划的返回值

dp.back

代码

核心代码

class Solution {
		public:
			vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
				vector<vector<int>> neiBo(n);
				for (int i = 0; i + 1 < n; i++) {
					neiBo[i].emplace_back(i + 1);
				}
				vector<int> ans;
				for (const auto& v : queries) {
					neiBo[v[0]].emplace_back(v[1]);
					vector<int> dp(n, INT_MAX / 2);
					dp[0] = 0;
					for (int i = 0; i < n; i++) {
						for (const auto& j : neiBo[i]) {
							dp[j] = min(dp[j] , dp[i] + 1);
						}
					}
					ans.emplace_back(dp.back());
				}
				return ans;
			}
		};

代码

核心代码

int n;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			n = 5, queries = { {2, 4}, {0, 2}, {0, 4} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 3,2,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, queries = { {0, 3}, {0, 2} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 1,1 }, res);
		}

单元测试

int n;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			n = 5, queries = { {2, 4}, {0, 2}, {0, 4} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 3,2,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, queries = { {0, 3}, {0, 2} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 1,1 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

120页PPT讲解ChatGPT如何与财务数字化转型的业财融合

此方案主要聚焦于利用ChatGPT技术与数字化转型推动业财融合&#xff0c;实现企业的价值最大化。首先&#xff0c;通过ChatGPT技术&#xff0c;企业可以构建生成式对话机器人&#xff0c;自动回答常见问题&#xff0c;减轻人工客服的压力&#xff0c;提高响应速度。这种机器人具…

旋转框目标检测自定义数据集训练测试流程

文章目录 前言一、数据集制作二、模型训练2.1 划分训练集验证集:2.2 配置yaml文件:2.3 训练 前言 旋转框目标检测&#xff08;Rotated bounding box object detection&#xff09;是计算机视觉领域的一项技术&#xff0c;它用于检测图像中具有任意方向的目标。与传统的水平矩形…

【QSS样式表 - ⑥】:QPushButton控件样式

文章目录 QPushBUtton控件样式QSS示例 QPushBUtton控件样式 常用子控件 常用伪状态 QSS示例 代码&#xff1a; QPushButton {background-color: #99B5D1;color: white;font-weigth: bold;border-radius: 20px; }QPushButton:hover {background-color: red; }QPushButton:p…

C# Random 随机数 全面解析

总目录 前言 一、Random 是什么&#xff1f; 1. 简介 表示伪随机数生成器&#xff0c;这是一种能够产生满足某些随机性统计要求的数字序列的算法。 public class Random继承&#xff1a;Object → Random 2. 构造函数 3. 属性 4. 方法 二、Random 的使用 1. Next() 或 Nex…

Linux网络——UDP的运用

Linux网络——UDP的运用 文章目录 Linux网络——UDP的运用一、引入二、服务端实现2.1 创建socket套接字2.2 绑定bind2.3 启动服务器2.4 IP的绑定的细节2.5 读取数据recvfrom 三、用户端实现3.1 绑定问题3.2 发送数据sendto 四、代码五、UDP实现网络聊天室&#xff08;简易版&am…

IDEA使用Alt + Enter快捷键自动接受返回值一直有final修饰的问题处理

在使用IDEA的过程中&#xff0c;使用快捷键Alt Enter在接收返回值时&#xff0c;可以快速完成参数接收&#xff0c;但前面一直会出现接收参数前面有final修饰的情况&#xff0c;效果如下所示&#xff1a; 看着真烦人呢&#xff0c;我们会发现在接受到返回值是上方有个 Declare…

【小白51单片机专用教程】protues仿真AT89C51入门

课程特点 无需开发板0基础教学软件硬件双修辅助入门 本课程面对纯小白&#xff0c;因此会对各个新出现的知识点在实例基础上进行详细讲解&#xff0c;有相关知识的可以直接跳过。课程涉及protues基本操作、原理图设计、数电模电、kell使用、C语言基本内容&#xff0c;所有涉及…

软件设计与体系结构

1.简要说明什么是软件体系结构&#xff0c;软件体系结构模型&#xff0c;为什么要建立软件体系结构模型&#xff1f; 答&#xff1a;软件体系结构指一个软件系统在高层次上的结构化组织方式&#xff0c;包括系统的组成部分和各个部分之间的关系&#xff0c;以及它们与环境之间的…

位置式PID-控制步进电机-位置环-stm32

基本原理 1、软件设计 本闭环控制例程是在步进电机编码器测速例程的基础上编写的,这里只讲解核心的部分代码,有些变量的设置,头文件的包含等并没有涉及到,完整的代码请参考本章配套的工程。 我们创建了4个文件:bsp_pid.c和bsp_pid.h文件用来存放PID控制器相关程序,bsp_s…

汽车IVI中控开发入门及进阶(47):CarPlay开发

概述: 车载信息娱乐(IVI)系统已经从仅仅播放音乐的设备发展成为现代车辆的核心部件。除了播放音乐,IVI系统还为驾驶员提供导航、通信、空调、电源配置、油耗性能、剩余行驶里程、节能建议和许多其他功能。 ​ 驾驶座逐渐变成了你家和工作场所之外的额外生活空间。2014年,…

电力通信规约-104实战

电力通信规约-104实战 概述 104规约在广泛应用于电力系统远动过程中&#xff0c;主要用来进行数据传输和转发&#xff0c;本文将结合实际开发实例来讲解104规约的真实使用情况。 实例讲解 因为个人技术栈是Java&#xff0c;所以本篇将采用Java实例来进行讲解。首先我们搭建一…

AWS Transfer 系列:简化文件传输与管理的云服务

在数字化转型的今天&#xff0c;企业对文件传输、存储和管理的需求日益增长。尤其是对于需要大量数据交换的行业&#xff0c;如何高效、可靠地传输数据成为了一大挑战。为了解决这一难题&#xff0c;AWS 提供了一系列的文件传输服务&#xff0c;统称为 AWS Transfer 系列。这些…

动态规划<四> 回文串问题(含对应LeetcodeOJ题)

目录 引例 其余经典OJ题 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 引例 OJ 传送门Leetcode<647>回文子串 画图分析&#xff1a; 使用动态规划解决 原理&#xff1a;能够将所有子串是否是回文的信息保存在dp表中 在使用暴力方法枚举出所有子串&#xff0c;是…

stm32定时器输出比较----驱动步进电机

定时器输出比较理论 OC(Output Compare)输出比较输出比较可以通过比较CNT与CCR寄存器值的关系,来对输出电平进行置1、置0或翻转的操作,用于输出一定频率和占空比的PWM波形每个高级定时器和通用定时器都拥有4个输出比较通道高级定时器的前3个通道额外拥有死区生成和互补输出…

Windows电脑部署SD 3.5结合内网穿透随时随地生成高质量AI图像

文章目录 前言1. 本地部署ComfyUI2. 下载 Stable Diffusion3.5 模型3. 演示文生图4. 公网使用Stable Diffusion 3.5 大模型4.1 创建远程连接公网地址 5. 固定远程访问公网地址 前言 在数字化创意时代&#xff0c;AI技术的发展为我们带来了无限可能。尤其是对于那些追求高效和高…

Easysearch Java SDK 2.0.x 使用指南(二)

在 上一篇文章 中&#xff0c;我们介绍了 Easysearch Java SDK 2.0.x 的基本使用和批量操作。本文将深入探讨索引管理相关的功能&#xff0c;包括索引的创建、删除、开关、刷新、滚动等操作&#xff0c;以及新版 SDK 提供的同步和异步两种调用方式。 SDK 的对象构建有两种方式…

Scala——身份证号码查询籍贯

object Test_身份证查询籍贯 { def main(args: Array[String]): Unit { val code "42005200210030051".substring(0,2) println(code) //判断42是哪个省的 //湖北 // if(code "42"){ // println("42对应省份为&#xff1a;湖北") // }else…

分布式系统架构:限流设计模式

1.为什么要限流&#xff1f; 任何一个系统的运算、存储、网络资源都不是无限的&#xff0c;当系统资源不足以支撑外部超过预期的突发流量时&#xff0c;就应该要有取舍&#xff0c;建立面对超额流量自我保护的机制&#xff0c;而这个机制就是微服务中常说的“限流” 2.四种限流…

2024年11月 蓝桥杯青少组 STEMA考试 Scratch真题

2024年11月 蓝桥杯青少组 STEMA考试 Scratch真题&#xff08;选择题&#xff09; 题目总数&#xff1a;5 总分数&#xff1a;50 选择题 第 1 题 单选题 Scratch运行以下程宇后&#xff0c;小兔子会&#xff08; &#xff09;。 A. 变小 B. 变大 C. 变色 D. …

Pytorch | 从零构建ParNet/Non-Deep Networks对CIFAR10进行分类

Pytorch | 从零构建ParNet/Non-Deep Networks对CIFAR10进行分类 CIFAR10数据集ParNet架构特点优势应用 ParNet结构代码详解结构代码代码详解SSEParNetBlock 类DownsamplingBlock 类FusionBlock 类ParNet 类 训练过程和测试结果代码汇总parnet.pytrain.pytest.py 前面文章我们构…