当前位置: 首页 > news >正文

[M最短路] lc743. 网络延迟时间(spfa最短路+单源最短路)

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:743. 网络延迟时间

相关链接:

  • [图+最短路+模板] 五大最短路常用模板)

2. 题目解析

怎么讲呢,挺抽象的…很久没写最短路算法了。反正也是写出来了,但脱离了模板,把自己还给绕进去了…

这块还是按照模板来写吧。

至于具体的算法思想,看相关链接即可。


  • 时间复杂度 O ( n m ) O(nm) O(nm)
  • 空间复杂度 O ( 1 ) O(1) O(1)

标准 spfa

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<pair<int, int>> g[n + 1];for (auto& e : times) {int x = e[0], y = e[1], w = e[2];g[x].push_back({y, w});}// 标准 spfa 算法queue<int> q; vector<int> dist(n + 1, 1e9);   // 注意这里初始化的是最大值vector<bool> st(n + 1, false);q.push(k);dist[k] = 0;while (q.size()) {auto x = q.front(); q.pop();st[x] = false; // x 不在队列中for (auto& [y, w] : g[x]) { // 更新 x 点临边if (dist[y] > dist[x] + w) { // 如果 y 点可以被 x 点更新dist[y] = dist[x] + w; // 则更新if (!st[y]) { // 如果 y 不在队列中,则加入q.push(y);st[y] = true;}}}}int res = -1e9;for (int i = 1; i <= n; i ++ ) {if (dist[i] == 1e9) return -1;  // 这里也是拿最大值进行的判断res = max(res, dist[i]);}return res;}
};

以下是 y 总写的 spfa 模板,大同小异。

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];class Solution {
public:void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}void spfa(int start) {queue<int> q;q.push(start);memset(dist, 0x3f, sizeof dist);dist[start] = 0;while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];if (!st[j]) {q.push(j);st[j] = true;}}}}}int networkDelayTime(vector<vector<int>>& times, int n, int k) {memset(h, -1, sizeof h);idx = 0;for (auto& e: times) {int a = e[0], b = e[1], c = e[2];add(a, b, c);}spfa(k);int res = 1;for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);if (res == INF) res = -1;return res;}
};作者:yxc
链接:https://www.acwing.com/activity/content/code/content/1011633/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2024年11月26日00:08:57
这里不知道随便写的 spfa 也过了…
不要留下坏印象…

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> g(n, vector<pair<int, int>>{});for (auto& e : times) {int x = e[0] - 1, y = e[1] - 1, w = e[2];g[x].push_back({y, w});}queue<int> q; vector<int> st(n, -1);  // 即是 st 又是 dist,用 -1 做状态标记位k = k - 1;q.push(k);st[k] = 0;while (q.size()) {auto x = q.front(); q.pop();for (auto& [y, w] : g[x]) {if (st[y] == -1 || st[y] > st[x] + w) { // 这里其实参考的是 dij 算法,又像 spfast[y] = st[x] + w;q.push(y);}}}int res = -1e9;for (int& x : st) {if (x == -1) return -1;res = max(res, x);}return res;}
};

相关文章:

[M最短路] lc743. 网络延迟时间(spfa最短路+单源最短路)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接&#xff1a;743. 网络延迟时间 相关链接&#xff1a; [图最短路模板] 五大最短路常用模板) 2. 题目解析 怎么讲呢&#xff0c;挺抽象的…很久没写最短路算法了。反正也是写出来了&#xff0c;但脱离了模板&#xff0c;把…...

MySQL 中的锁

MySQL 中的锁&#xff1a;全面解析与应用指南 在 MySQL 数据库的复杂世界里&#xff0c;锁是确保数据一致性、完整性以及并发控制的关键机制。无论是简单的小型应用还是复杂的企业级系统&#xff0c;深入理解 MySQL 中的锁对于优化数据库性能、避免数据冲突和错误都具有至关重要…...

【动手学电机驱动】STM32-FOC(8)MCSDK Profiler 电机参数辨识

STM32-FOC&#xff08;1&#xff09;STM32 电机控制的软件开发环境 STM32-FOC&#xff08;2&#xff09;STM32 导入和创建项目 STM32-FOC&#xff08;3&#xff09;STM32 三路互补 PWM 输出 STM32-FOC&#xff08;4&#xff09;IHM03 电机控制套件介绍 STM32-FOC&#xff08;5&…...

【C++11】尽显锋芒

(续) 一、可变参数模板 C11支持可变参数模板&#xff0c;也就是说支持可变数量参数的函数模板和类模板&#xff0c;可变数目的参数被称 为参数包&#xff0c;存在两种参数包&#xff1a;模板参数包&#xff0c;表示零或多个模板参数&#xff1b;函数参数包&#xff1a;表示零…...

掌握控制流的艺术:Go语言中的if、for和switch语句

标题:掌握控制流的艺术:Go语言中的if、for和switch语句 在Go语言的编程世界中,控制流语句是构建程序逻辑的基石。if语句、for循环和switch语句是我们最常用的控制流工具,它们让我们能够根据不同的条件执行不同的代码块。本文将深入探讨这些语句的使用方法、技术细节和实际…...

飞书会话消息左右排列

飞书会话消息左右排列 1. 飞书登录后&#xff0c;点击头像&#xff0c;弹出菜单有个按钮设置 2. 3....

.net 支持跨平台(桌面)系列技术汇总

1. 首先微软老大哥的.net core 。 .NET Core 是微软开发的一个跨平台、高性能的开源框架&#xff0c;用于构建云和互联网连接的新型应用。 它允许开发者在 Windows、macOS 和 Linux 上使用喜爱的开发工具进行开发&#xff0c;并支持部署到云或本地环境。 .NET Core 是对 .NET …...

springboot 静态资源访问

最近在学习springboot&#xff0c;在学习中一个静态资源访问&#xff0c;难道了我三天&#xff0c;在网上找了很多的资料&#xff0c;又是配置&#xff0c;又是重写WebMvcConfigurationSupport&#xff0c;因为以前没有接触&#xff0c;本来很简单的事情走了很多弯路&#xff0…...

【linux学习指南】初识Linux进程信号与使用

文章目录 &#x1f4dd;信号快速认识&#x1f4f6;⽣活⻆度的信号&#x1f4f6; 技术应⽤⻆度的信号&#x1f309; 前台进程&#xff08;键盘&#xff09;&#x1f309;⼀个系统函数 &#x1f4f6;信号概念&#x1f4f6;查看信号 &#x1f320; 信号处理&#x1f309; 忽略此信…...

L1G1000 书生大模型全链路开源开放体系笔记

关卡任务 观看本关卡视频后&#xff0c;写一篇关于书生大模型全链路开源开放体系的笔记。 视频链接&#xff1a;【书生浦语大模型全链路开源体系】 : 书生浦语大模型开源开放体系_哔哩哔哩_bilibili 书生大模型全链路开源开放体系笔记 在人工智能领域&#xff0c;大模型的…...

亚信安全与飞书达成深度合作

近日&#xff0c;亚信安全联合飞书举办的“走近先进”系列活动正式走进亚信。活动以“安全护航信息化 共筑数字未来路”为主题&#xff0c;吸引了众多数字化转型前沿企业的近百位领导参会。作为“走近先进”系列的第二场活动&#xff0c;本场活动更加深入挖掘了数字化转型的基础…...

深入讲解Spring Boot和Spring Cloud,外加图书管理系统实战!

很抱歉&#xff0c;我的疏忽&#xff0c;说了这么久还没有给大家详细讲解过Spring Boot和Spring Cloud,那今天给大家详细讲解一下。 大家可以和下面这三篇博客一起看&#xff1a; 1、Spring Boot 和 Spring Cloud 微服务开发实践详解https://blog.csdn.net/speaking_me/artic…...

【三维生成】Edify 3D:可扩展的高质量的3D资产生成(英伟达)

标题&#xff1a;Edify 3D: Scalable High-Quality 3D Asset Generation 项目&#xff1a;https://research.nvidia.com/labs/dir/edify-3d demo&#xff1a;https://build.nvidia.com/Shutterstock/edify-3d 文章目录 摘要一、前言二、多视图扩散模型2.1.消融研究 三、重建模型…...

Java求职招聘网站开发实践

一、项目介绍 本文将介绍如何使用Java技术栈开发一个求职招聘网站。该网站主要实现求职者和招聘方的双向选择功能&#xff0c;包含用户管理、职位发布、简历投递等核心功能。 二、技术选型 后端框架&#xff1a;Spring Boot 2.7.0数据库&#xff1a;MySQL 8.0前端框架&#…...

一文详细了解websocket应用以及连接断开的解决方案

文章目录 websocketvite 热启动探索websocket -心跳websocket 事件监听应用过程中问题总结 websocket Websocket简介 定义和工作原理 Websocket是一种在单个TCP连接上进行全双工通信的协议。与传统的HTTP请求 - 响应模式不同&#xff0c;它允许服务器主动向客户端推送数据。例…...

如何做含有identify抓信号的fpga版本(image或者Bit)

在数字的FPGA debug中除了ila就是identify了&#xff0c;identify是synopsys公司的RTL级的调试工具。要用起来idetify&#xff0c;第一步就是要做出含有identify的信号的FPGA版本&#xff0c;quartus的是image&#xff0c;Ximlinx的是Bit或者Bin文件。具体有以下几步&#xff1…...

AIGC实践-使用Amazon Bedrock的SDXL模型进行文生图

一、Bedrock 简介 Amazon Bedrock 是 Amazon Web Services (AWS) 提供的一种生成式 AI 服务。通过 Bedrock&#xff0c;用户可以方便地使用多种基础模型&#xff08;Foundation Models&#xff09;&#xff0c;包括 OpenAI 的 GPT、Anthropic 的 Claude 等。这些模型可以用于各…...

【源码】Sharding-JDBC源码分析之SQL中分片键路由ShardingSQLRouter的原理

Sharding-JDBC系列 1、Sharding-JDBC分库分表的基本使用 2、Sharding-JDBC分库分表之SpringBoot分片策略 3、Sharding-JDBC分库分表之SpringBoot主从配置 4、SpringBoot集成Sharding-JDBC-5.3.0分库分表 5、SpringBoot集成Sharding-JDBC-5.3.0实现按月动态建表分表 6、【…...

初学 flutter 环境变量配置

一、jdk&#xff08;jdk11&#xff09; 1&#xff09;配置环境变量 新增&#xff1a;JAVA_HOMEC:\Program Files\Java\jdk-11 //你的jdk目录 在path新增&#xff1a;%JAVA_HOME%\bin2&#xff09;验证是否配置成功&#xff08;cmd运行命令&#xff09; java java -version …...

蓝牙 AVRCP 协议详解

前言 随着无线音频设备的普及&#xff0c;蓝牙已经成为智能设备间通信的主流方式之一。除了传输音频流的 A2DP 协议外&#xff0c;AVRCP&#xff08;Audio/Video Remote Control Profile&#xff0c;音频/视频远程控制协议&#xff09;为用户提供了对蓝牙音频设备的控制能力&am…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

raid存储技术

1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划&#xff0c;涵盖存储系统的布局、数据存储策略等&#xff0c;它明确数据如何存储、管理与访问&#xff0c;为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...