力扣题解(新增道路查询后的最短距离I)

3243. 新增道路查询后的最短距离 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] 中的每个 ianswer[i] 是处理完 i + 1 个查询后,从城市 0 到城市 n - 1 的最短路径的长度

思路:

一开始尝试利用求最短路的prim,floy的算法,发现均会超时,因为那些算法是不只是求从0到n的最短边,还至少包括从从0到其余边的,因此考虑其他做法。对于求最短路问题,比较常见的做法是利用bfs遍历,就是保存当前所有的边,然后每次新增加一个边后,就暴力bfs搜索从0到n-1的最小距离。一共需要搜索数组长度(q)次,每次搜索最多需要n+q的时间(就是把所有边全遍历一遍),最后近似500*500的时间,不会超时。

class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<int>ans;vector<vector<int>>g(n);for(int i=0;i<n-1;i++)g[i].push_back(i+1);auto bfs=[&](int i){vector<int>q={0};bool st[1000];memset(st,false,sizeof st);for(int step=1;;step++){   vector<int>nxt;for(auto x:q){  for(auto y:g[x]){if(y==n-1)return step;if(!st[y])nxt.push_back(y),st[y]=true;}}q=nxt;}};for(int i=0;i<queries.size();i++){int a=queries[i][0],b=queries[i][1];g[a].push_back(b);ans.push_back(bfs(i));}return ans;}
};

此外,本题还会发现,如果你对一条从a到b的边进行更新,所影响的只会是b之后的边,对于b之前的边不会有任何变化,也可以考用dp动态递归,每次加入新的边之后,如果这条边不会影响从0到b的最短距离,就不会影响b之后的最短距离,那就不会变化。反之,如果影响了从0到b的最短距离,就需要对b之后的边进行重新计算,具体计算方法是对于一个大于b的点q,暴力遍历所有0--q-1中到q的边,然后看是否可以更新0到q的最短距离。因为是要找以q为终点的距离,因此设置这个边的数组的时候可以保存以j为终点的边在dis[j]中。

class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<vector<int>>from(n);vector<int>f(n);for(int i=1;i<n;i++)f[i]=i;vector<int>ans;for(auto e:queries){int a=e[0],b=e[1];from[b].push_back(a);if(f[b]>f[a]+1){f[b]=f[a]+1;for(int i=b+1;i<n;i++){f[i]=min(f[i],f[i-1]+1);for(auto k:from[i])f[i]=min(f[i],f[k]+1);}}ans.push_back(f[n-1]);}return ans;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

面向服务的软件工程——巨详细讲解商务流程建模符号 (BPMN),一篇章带你入门BPMN!!!(week1)

文章目录 一、前言二、重点概念三、BPMN元素讲解流对象1.活动任务(Task)子流程(sub-process)多实例活动连接对象序列流消息流关联泳道Artifacts数据对象组(Group)事件(Events)启动事件中间事件结束事件边界事件边界事件1边界事件2小疑问?网关参考文献:一、前言 在我们…

模拟实现~简易通讯录

一.前言 今天给小伙伴们分享的是运用结构体以及指针等相关C语言知识实现一个简易版的通讯录。咱们写的通讯录的功能主要包括添加及删除联系人&#xff0c;修改联系人信息&#xff0c;显现所有联系人&#xff0c;查找已添加联系人&#xff0c;以及对联系人进行排序&#xff0c;…

0成本添加访问级监控

互联网的安全感这个概念源于阿里。顾名思义&#xff0c;让互联网的用户对于web产品能够产生足够的信任和依赖。特别是涉及到用户资金交易的站点&#xff0c;一次严重的用户资料泄露就可以彻底毁掉你的品牌。 然而当前阶段除了bat大部分互联网行业的企业对于网络安全给的重视都…

分布式系统稳定性建设-性能优化篇

分布式系统稳定性建设-性能优化篇 系统稳定性建设是系统工程的核心内容之一。以下是一些重要的方面: 架构设计: 采用模块化、松耦合的架构设计,以提高系统的可扩展性和可维护性。合理划分系统功能模块,降低单个模块的复杂度。定义清晰的接口和数据交换标准,确保各模块之间协调…

Web端高效BIM 3D可视化引擎HOOPS Communicator技术解析!

HOOPS Communicator是一款简单而强大的工业级高性能3D Web可视化开发包&#xff0c;专注于Web端工程图形渲染。采用了先进的流式加载方式&#xff0c;并支持服务端和客户端渲染&#xff0c;是可以在云端进行部署和无缝集成的新技术平台。 灵活且易于部署&#xff0c;可在以工程…

C/C++实现tcp客户端和服务端的实现(从零开始写自己的高性能服务器)

目录 tcp客户端通信流程 tcp客户端设计 1、创建通信对象 2、链接服务器 3、发送数据 / 读取数据 4、关闭通信 tcp服务端设计 1、创建通信对象 2、绑定服务器地址信息 3、设置服务器为监听模式 4、接收客户的链接请求 编写tcp客户端和服务端&#xff0c;实现双向通信…

C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程

引言 C 标准模板库&#xff08;STL&#xff09;提供了一组功能强大的容器类&#xff0c;用于存储和操作数据集合。不同的容器具有独特的特性和应用场景&#xff0c;因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C 的开发者来说&#xff0c;了解这些容…

快速上手并使用Muduo库

Muduo muduo库是基于主从reactor模型的高性能服务器&#xff08;高并发服务器&#xff09;框架 reactor模型&#xff1a;基于事件触发的模型&#xff08;基于epoll进行IP事件监控&#xff09; 主从reactor模型&#xff1a;将IO事件监控有进行进一步的层次划分 主reactor&#x…

深入解析【C++多态】:探索面向对象编程中的动态绑定与行为多样性和多态的核心概念与应用实践

&#x1f31f;个人主页&#xff1a;落叶 &#x1f31f;当前专栏: C专栏 目录 多态的概念 多态的定义及实现 实现多态还有两个必须重要条件 虚函数 虚函数的重写/覆盖 多态场景的⼀个选择题 虚函数重写的⼀些其他问题 协变(了解进行) 析构函数的重写 override 和 final关…

React Native Mac 环境搭建

下载 Mac 版Android Studio 下载 安装 JDK 环境 Flutter 项目实战-环境变量配置一 安装 Node.js 方式一 通过Node.js 官网下载 下载完成后点击安装包进行安装 安装完成

【Word】一键批量引用论文上标——将正文字体改为上标格式

【Word】一键批量引用论文上标——将正文字体改为上标格式 写在最前面Word一键批量引用论文上标技巧分享核心思路&#xff1a;Word 替换功能 通配符步骤详解1. 打开 Word 替换功能2. 输入通配符模式3. 设置替换格式为上标4. 批量替换 实际效果展示技巧扩展 &#x1f308;你好呀…

深入探索Python数据可视化:自定义颜色映射、标签与进阶技巧

目录 一、自定义颜色映射&#xff08;Cmap&#xff09; 1. 内置Cmap类型 2. 使用内置Cmap 3. 自定义Cmap 二、标签添加 1. 在散点图上添加标签 2. 在折线图上标记关键点 3. 在柱状图上添加标签 三、进阶技巧 1. 多图形布局 2. 添加图例 3. 3D数据可视化 四、总结 …

【Java SE】数据库连接池

数据库连接池是一个管理数据库连接的容器。它的主要作用是分配和管理数据库连接&#xff0c;允许应用程序重复使用现有的连接&#xff0c;而不是每次都重新建立新的连接。此外&#xff0c;连接池会释放那些空闲时间超过最大限制的连接&#xff0c;从而避免因未及时释放连接而造…

FastAPI重载不生效?解决PyCharm中Uvicorn无法重载/重载缓慢的终极方法!

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 重载缓慢 📒📝 问题概述🚨 相关原因📝 解决方案一📝 解决方案二📝 解决方案三📝 解决方案四⚓️ 相关链接 ⚓️📖 介绍 📖 在使用FastAPI开发时,reload=True 本应让你在修改代码后自动重启服务,提升开发效率…

CPU算法分析LiteAIServer视频智能分析平台未戴安全帽检测算法

随着人工智能技术的不断进步&#xff0c;CPU算法分析在视频智能分析平台中的应用日益广泛。特别是在工地安全管理领域&#xff0c;未戴安全帽检测算法已成为一项关键的安全保障措施。LiteAIServer视频智能分析平台通过结合CPU的高效运算能力和先进的深度学习算法&#xff0c;实…

两网站定时数据exchange项目详解

功能说明 A网站&#xff1a;用户可以通过表单输入嫌疑人信息&#xff0c;这些信息会被存储在内存中&#xff0c;并通过API接口返回。B网站&#xff1a;通过API接口接收从A网站同步过来的嫌疑人数据&#xff0c;并显示这些数据。主应用&#xff1a;使用APScheduler每隔1分钟从A…

【云计算】腾讯云架构高级工程师认证TCP--考纲例题,知识点总结

【云计算】腾讯云架构高级工程师认证TCCP–知识点总结&#xff0c;排版整理 文章目录 1、云计算架构概论1.1 五大版块知识点&#xff08;架构设计&#xff0c;基础服务&#xff0c;高阶技术&#xff0c;安全&#xff0c;上云&#xff09;1.2 课程详细目录1.3 云基础架构设计1.4…

sql server查看当前正在执行的sql

#统计某类sql执行次数&#xff0c;并按总体cpu消耗时间降序排序 with a as ( select er.session_id,db_name(er.database_id) as DBNAME,sy.last_batch AS 最后执行时间, er.cpu_time ,er.total_elapsed_time/1000 as sum_elapsed_time_s, CAST(csql.text AS varchar(8000)) A…

【UE5】Slider控件样式

实现根据滑柄位置确定滑条样式的功能&#xff0c;效果如下。 效果 步骤 1. 添加Slider控件和文本控件&#xff0c;其中文本控件用于显示滑条的值 2. 文本控件绑定变量&#xff0c;这里变量为“Year” 3. 当滑条的值变更后&#xff0c;设置“Year”的值&#xff0c;然后调用函…

JVM性能分析工具JProfiler的使用

一、基本概念 JProfiler&#xff1a;即“Java Profiler”&#xff0c;即“Java分析器”或“Java性能分析工具”。它是一款用于Java应用程序的性能分析和调试工具&#xff0c;主要帮助开发人员识别和解决性能瓶颈问题。 JVM&#xff1a;即“Java Virtual Machine”&#xff0c…