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

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

news 来源：原创 2025/7/21 14:26:18

文章目录

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

1. 题目来源

链接：743. 网络延迟时间

2. 题目解析

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

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

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

时间复杂度： $O (nm)$
空间复杂度： $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. 题目来源链接：743. 网络延迟时间相关链接： [图最短路模板] 五大最短路常用模板) 2. 题目解析怎么讲呢，挺抽象的…很久没写最短路算法了。反正也是写出来了，但脱离了模板，把…...

编程日记 2025/7/21 14:26:18

使用nvm下载多个版本node后提示vue不是内部或外部命令，执行vue create报.vuerc错误

一、使用nvm后执行含vue的相关命令提示vue不是内部或外部命令前言：之前有项目需要切换node版本，我把node卸载了然后使用nvm下载多个版本的node。现在想通过vue create搭建vue2的项目时提示vue不是内部或外部命令，执行npm i vue/cli后仍然无…...

编程日记 2025/7/20 22:50:40

高端服务器可以防护哪些攻击？

高端服务器，尤其是那些专门设计用于防御网络攻击的高防服务器，能够提供多种层次的防护，以抵御不同类型的网络攻击。以下是高端服务器可以防御的主要攻击类型： 1. DDoS攻击（分布式拒绝服务攻击） 带宽消耗攻…...

编程日记 2025/7/21 1:36:43

助力花生作物智能化采摘，基于嵌入式端超轻量级模型LeYOLO全系列【n/s/m/l】参数模型开发构建花生种植采摘场景下花生果实智能检测计数系统

秋天，是大地回馈辛勤耕耘者的季节，金黄的稻田、硕果累累的果园、还有那一片片郁郁葱葱的花生地，共同绘制出一幅幅丰收的画卷。对于农民而言，秋收不仅仅是收获的季节，更是他们与土地情感交织、汗水与希望交织的见证。花…...

编程日记 2025/7/19 17:32:46

物联网无线局域网WiFi开发(二)：WiFi_RTOS_SDK

一、编译工程模板 （一）搭建app目录在SDK目录下新建app目录 cd 到examples目录下拷贝smart_config下所有文件到app目录下 cd 到app目录下查看文件是否拷贝成功 (二)修改gen_misc.sh vim 打开gen_misc.sh进行编辑修改SDK_PATH为当前SDK路径&#xf…...

编程日记 2025/7/20 16:20:01

创建docker-compose.yaml文件输入docker-compose配置 version: 3.8 services:gitlab:image: gitlab/gitlab-ce:15.11.2-ce.0restart: alwayscontainer_name: gitlab-ceprivileged: truehostname: 192.168.44.235environment:TZ: Asia/ShanghaiGITLAB_OMNIBUS_CONFIG: |exter…...

编程日记 2025/7/13 19:50:43

替换Nacos的MySQL驱动

前言：替换Nacos的MySQL驱动能实现使Nacos支持MySQL8.0及以上版本的MySQL数据库注：下述教程会使用命令先解压Nacos的jar包然后重新用命令把Nacos压缩成jar包，不然直接用压缩工具替换MySQL驱动后的Nacos是会启动不起来的（因为没有替…...

编程日记 2025/7/18 22:54:39

链表内指定区间反转

描述将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。例如： 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m2,n4m2,n4, 返回 1→4→3→2→5→NULL1→4→3→2→5→NULL. …...

编程日记 2025/7/21 14:01:27

jmeter5.6.3安装教程

一、官网下载需要提前配置好jdk的环境变量 jmeter官网：https://jmeter.apache.org/download_jmeter.cgi 选择点击二进制的zip文件下载成功后，默认解压下一步，更改安装路径就行(我安装在D盘) 实用jmeter的bin目录作为系统变量然后把这…...

编程日记 2025/7/15 5:04:34

JavaScript高级程序设计基础（五）

上接语言基础：JavaScript高级程序设计基础（四） 本节内容较简单，有一定语言基础的可以跳过 2.5 语句 2.5.1 if语句具体作用不做过多赘述。需要注意的是，在判断条件里会自动调用Boolean()；并且在执行语句…...

编程日记 2025/7/20 22:46:48

Stable Diffusion 3 部署笔记

SD3下载地址：https://huggingface.co/stabilityai/stable-diffusion-3-medium/tree/main https://huggingface.co/spaces/stabilityai/stable-diffusion-3-medium comfyui 教程： 深度测评：SD3模型表现如何？实用教程助你玩转Stabl…...

编程日记 2025/7/21 11:03:42

深度解析：Vue 自定义指令到底是什么？快来了解

自定义指令的概述在Vue中，自定义指令是开发者自定义的，用来在DOM元素上执行特定操作的功能。Vue本身提供了多种内建指令（如v-bind, v-model, v-for, v-if等），但有时候我们需要创建自己的指令来实现一些特殊功能。这些功能可以是对DOM的直接操作，或者是为了满足特定的业…...

编程日记 2025/7/19 20:04:41

CVE-2022-4230

打开什么都没有使用dirsearch扫描到一个wp-admin 访问wp-admin是一个登陆页面账号密码都在标题中登陆后是这个页面在WP Statistics < 13.2.9 – 经过身份验证的 SQLi |CVE 2022-4230 |插件漏洞 (wpscan.com)中，里边有一段对漏洞的描述。 https://wpscan.com…...

编程日记 2025/7/21 6:17:38

什么是 WPF 中的依赖属性？有什么作用？

依赖属性（Dependency Property）是 WPF 的一个核心概念，它为传统的 .NET 属性提供了增强功能，支持绑定、样式、动画和默认值等功能。通过依赖属性，WPF 提供了一种灵活的数据驱动的方式来处理 UI 属性。 1. 什么是依赖属…...

编程日记 2025/7/18 19:30:23

『 Linux 』网络层 - IP协议 (二)

文章目录路由NAT技术分片与组装分片的组装IP协议分片的短板路由通常情况路由器具备了一个非常重要的功能,即构建子网; 同时路由器需要实现跨网络通信,说明路由器必须存在两个或以上的IP地址,通常在路由器中可以看到几个接口,分别是一个WAN口和几个LAN口; WAN口IP被称为公网I…...

编程日记 2025/7/16 14:56:09

Linux开发者的CI/CD（11）jenkins变量

文章目录 1. **环境变量 (Environment Variables)**常见的环境变量：示例：2. **构建参数 (Build Parameters)**常见的构建参数类型：示例：3 **在 `stages` 块内定义局部变量**示例：使用 `script` 步骤定义局部变量4 变量引用陷阱在 Jenkins 中，变量是自动化流程中非常重要的…...

编程日记 2025/7/16 15:15:01

Python和R荧光分光光度法

🌵Python片段 Python在处理荧光分光光度法数据方面非常强大，得益于其丰富的数据处理和可视化库，可以轻松实现从数据读取到分析的完整流程。荧光分光光度法用于测量物质在激发光照射下发出的荧光强度，常用于定量分析和特性研究。 …...

编程日记 2025/7/20 15:19:20

理解clickhouse 里的分区和分片键区别

文章目录分片分区两分片，0副本的cluster 分片 CREATE TABLE logs_distributed AS logs_local ENGINE Distributed(cluster_name, -- 集群名称database_name, -- 数据库名称logs_local, -- 本地表名cityHash64(user_id) -- 分片键&#xf…...

编程日记 2025/7/19 21:52:26

【数据结构笔记】习题

渐进分析【2010-THU-Mid】f(n) O(g(n))，当且仅当g(n) Ω(f(n))。（√） 【2010-THU-Mid】若f(n) O(n^2)且g(n) O(n)，则以下结论正确的是（AD） A. f(n) g(n) O(n^2) B. f(n) / g(n) O(n) C. g(n) O(f(…...

编程日记 2025/7/19 1:10:46

非交换几何与黎曼ζ函数：数学中的一场革命性对话

非交换几何与黎曼ζ函数：数学中的一场革命性对话非交换几何（Noncommutative Geometry, NCG）是数学的一个分支领域，它将经典的几何概念扩展到非交换代数的框架中。非交换代数是一种结合代数，其中乘积不是交换性的&…...

编程日记 2025/7/20 11:15:53

【c++】模板详解(2)

🌟🌟作者主页：ephemerals__ 🌟🌟所属专栏：C 目录前言一、非类型模板参数二、模板的特化 1. 概念 2. 场景举例 3. 函数模板的特化 4. 类模板的特化全特化偏特化 1. 部分特化 2. 对参数的…...

编程日记 2025/7/20 2:54:01

DICOM图像处理：深入解析DICOM彩色图像中的Planar配置及其对像素数据解析处理的实现

引言在DICOM（Digital Imaging and Communications in Medicine）标准中，彩色图像的存储与显示涉及多个关键属性，其中**Planar Configuration（平面配置）**属性（标签 (0028,0006)）尤为重要。当遇到彩色DICOM图像在浏览时被错误地分割为9张小图，而实际应显示为一…...

编程日记 2025/7/18 13:35:15

【青牛科技】D3308 一块带有 ALC 的双通道前置放大器。它适用于立体声收录机和盒式录音机。

概述： D3308 是一块带有 ALC 的双通道前置放大器。它适用于立体声收录机和盒式录音机。采用 SIP9、SOP14 的封装形式封装。主要特点：  带内置 ALC 回路的双通道均衡放大器。  低噪声： VNI1.0V（典型值）。  开环…...

编程日记 2025/7/18 20:01:43

goframe开发一个企业网站 MongoDB 完整工具包18

1. MongoDB 工具包完整实现 (mongodb.go) package mongodbimport ("context""fmt""time""github.com/gogf/gf/v2/frame/g""go.mongodb.org/mongo-driver/mongo""go.mongodb.org/mongo-driver/mongo/options" )va…...

编程日记 2025/7/16 9:47:52

自动驾驶3D目标检测综述（四）

前三篇分别介绍了前四章的内容： 第一篇（介绍、摘要和背景）：自动驾驶3D目标检测综述（一）_3d 目标检测-CSDN博客第二篇（第三章基于激光雷达的3D目标检测）：自动驾驶3D目…...

编程日记 2025/7/5 7:13:54

远程控制软件：探究云计算和人工智能的融合

在数字化时代，远程控制工具已成为我们工作与生活的重要部分。用户能够通过网络远程操作和管理另一台计算机，极大地提升了工作效率和便捷性。随着人工智能（AI）和云计算技术的飞速发展，远程控制工具也迎来了新的发展机遇…...

编程日记 2025/7/20 5:35:26

3ds Max2024软件详细安装教程+中文安装包（永久使用）

[名称]：3ds Max2024 [大小]：5.07GB [语言]：简体中文 [安装环境]：Win11/Win10 软件介绍 3DS Max是一款三维建模和渲染软件,可以创造宏伟的游戏世界,布置精彩绝伦的场景以实现设计可视化,并打造身临其境的虚拟现实 (VR) ...在广告…...

编程日记 2025/7/18 23:06:01

深入解析 Spring MVC：架构、组件与最佳实践

文章目录 1. **DispatcherServlet**2. **HandlerMapping**3. **HandlerAdapter**4. **Controller**5. **ModelAndView**6. **ViewResolver**7. **View** 工作流程配置方式XML 配置Java 配置最佳实践示例项目项目目录结构控制器 (HelloWorldController.java)服务层 (HelloWorld…...

编程日记 2025/7/20 18:26:37

专题二十三_动态规划_回文串系列问题_算法专题详细总结

目录动态规划回文串系列问题 1. 回⽂⼦串（medium） 解析： 解决回文串问题，这里提供三个思路： 1.中心扩展法：n^2 / 1 2.马拉车算法：n / n 3.动态规划算法：n^2 / n^2 1.状态表…...

编程日记 2025/7/8 1:59:10

Linux操作系统学习---初识环境变量

目录编辑环境变量的概念： 小插曲：main函数的第一、二个参数获取环境变量信息： 1.main函数的第三个参数 2.查看单个环境变量 3.c语言库函数getenv() 和环境变量相关的操作指令： 1.export---导出环境变量： 2.unse…...

编程日记 2025/7/20 10:12:30

通过map文件了解堆栈分配(STM32、MDK5)--避免堆栈溢出

在最近的一个项目的开发中，每当调用到一个函数，程序就直接跑飞。debug跟进去看不出什么逻辑错误，但发现函数内局部变量声明之后，全局变量的值被清零，后来查看局部变量地址已经超出栈的范围，于是确定是栈溢出。如果不稍微了解一下堆栈，在开发过程中可能碰到各种奇怪的错误…...

编程日记 2025/7/18 15:12:24

设计模式——状态模式

定义状态模式（State Pattern）是一种行为设计模式。它允许一个对象在其内部状态改变时改变它的行为。对象看起来好像修改了它的类，从直观上看，就像是对象根据自身的状态来动态地切换行为方式。结构组成环境（Conte…...

编程日记 2025/7/19 5:07:13

没有技术背景考软考高级选什么科目呀？

没有技术背景的外行小白特别推荐考取信息系统项目管理师 ，也就是软考高项！ 软考高项是软考高级资格考试中相对最容易的一门，同时也是报考人数最多的一门。为什么选择软考高项呢？ 以我自己的经历为例。刚进入职场时&#xf…...

编程日记 2025/7/15 15:13:25

大语言模型---梯度的简单介绍；梯度的定义；梯度计算的方法

1. 梯度介绍如果我们在一座山上（一个山的坡度有很多，陡峭的，平缓的），想要从山顶下山。而梯度就像告诉我们如何沿着最陡的下坡路线走，以尽快到达山脚（最低点）。 2. 梯度的定义梯度…...

编程日记 2025/7/18 13:48:40

【R语言管理】Pycharm配置R语言及使用Anaconda管理R语言虚拟环境

目录使用Anaconda创建R语言虚拟环境1. 安装Anaconda2. 创建R语言虚拟环境 Pycharm配置R语言1. 安装Pycharm2. R Language for IntelliJ插件参考使用Anaconda创建R语言虚拟环境 1. 安装Anaconda Anaconda的安装可参见另一博客-【Python环境管理工具】Anaconda安装及使用教程…...

编程日记 2025/7/16 21:56:28

蓝桥杯每日真题 - 第24天

题目：（货物摆放） 题目描述（12届 C&C B组D题） 解题思路： 这道题的核心是求因数以及枚举验证。具体步骤如下： 因数分解： 通过逐一尝试小于等于的数，找到 n 的所有因数…...

编程日记 2025/7/20 22:47:24

mac 如何查看 export NVM_NODEJS_ORG_MIRROR=https://npm.taobao.org/mirrors/node 是否正确

在 macOS 上，如果你想查看环境变量 NVM_NODEJS_ORG_MIRROR 是否已正确设置为 https://npm.taobao.org/mirrors/node，你可以按照以下步骤进行检查： 1. 检查当前环境变量值打开终端并运行以下命令来查看 NVM_NODEJS_ORG_MIRROR 环境变量的当…...

编程日记 2025/7/16 20:02:25

Android 单元测试的各种环境问题记录

报错记录 failed to configure packages targetSdkVersion failed to configure com.demo.test.SettingsActivityTest.testOnCreate_withNullSavedInstanceState: Package targetSdkVersion34 > maxSdkVersion32 java.lang.IllegalArgumentException: failed to configure …...

编程日记 2025/7/20 23:18:31

文章目录

1. 题目来源

2. 题目解析

相关文章：