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

【CS.AL】算法核心之贪心算法 —— 力扣(LeetCode)743. 网络延迟时间 - Dijkstra算法题解

文章目录

    • 题目描述
    • References

题目描述

743. 网络延迟时间 - 力扣(LeetCode)

N 个网络节点,标记为 1N

给定一个列表 times,其中 times[i] = (u, v, w) 表示有一条从节点 u 到节点 v 的时延为 w 的有向边。

现在,我们从某个节点 K 发送一个信号。需要多少时间才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1

示例:

输入: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出: 2

可以使用 Dijkstra 算法来解决这个问题。算法的步骤如下:

  1. 构建邻接表:将输入的 times 转换成图的邻接表表示。 Ref. 【CS.DS】数据结构 —— 图:深入了解三种表示方法之邻接表(Adjacency List)
  2. 初始化数据结构:距离数组 dist[],所有节点的距离初始化为无穷大,起点的距离设为 0;优先级队列 pq 存储每个节点及其当前已知的最短距离。
  3. 执行 Dijkstra 算法:使用优先级队列选择当前距离起点最近的节点,更新其邻接节点的距离,并将更新后的节点加入队列。
  4. 计算结果:在所有节点都收到信号时,返回最大的距离;如果有节点未收到信号,返回 -1
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>using namespace std;int networkDelayTime(vector<vector<int>>& times, int N, int K) {// 构建图的邻接表unordered_map<int, vector<pair<int, int>>> graph;for (const auto& time : times) {int u = time[0], v = time[1], w = time[2];graph[u].emplace_back(v, w);}// 初始化距离表vector<int> dist(N + 1, INT_MAX);dist[K] = 0;// 优先队列,按距离从小到大排序priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.emplace(0, K);while (!pq.empty()) {auto [current_dist, u] = pq.top();pq.pop();if (current_dist > dist[u]) {continue;}for (const auto& [v, w] : graph[u]) {int distance = current_dist + w;if (distance < dist[v]) {dist[v] = distance;pq.emplace(distance, v);}}}int max_dist = 0;for (int i = 1; i <= N; ++i) {if (dist[i] == INT_MAX) {return -1;}max_dist = max(max_dist, dist[i]);}return max_dist;
}int main() {vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};int N = 4;int K = 2;int result = networkDelayTime(times, N, K);if (result == -1) {cout << "无法使所有节点都收到信号" << endl;} else {cout << "所有节点都收到信号所需的时间: " << result << endl;}return 0;
}
  • 构建图的邻接表
    • 我们使用 unordered_map 将每个节点的邻接节点及其权重存储起来。
  • 初始化距离数组和优先级队列
    • 距离数组 dist 用于记录从起点到每个节点的最短距离,初始时所有距离设为无穷大,起点的距离设为 0。
    • 优先级队列 pq 用于高效选择当前距离最短的节点,初始时将起点入队。
  • Dijkstra 算法
    • 每次从优先级队列中取出距离最短的节点,更新其邻接节点的距离,并将更新后的节点加入队列。
  • 计算结果
    • 遍历距离数组,找到所有节点中最大的距离作为结果。如果有节点的距离仍为无穷大,返回 -1

References

  • 【CS.AL】算法核心之贪心算法:从入门到进阶
  • 【CS.DS】数据结构 —— 图:深入了解三种表示方法之邻接表(Adjacency List)
  • 【CS.AL】算法核心之贪心算法:从入门到进阶

相关文章:

【CS.AL】算法核心之贪心算法 —— 力扣(LeetCode)743. 网络延迟时间 - Dijkstra算法题解

文章目录 题目描述References 题目描述 743. 网络延迟时间 - 力扣&#xff08;LeetCode&#xff09; 有 N 个网络节点&#xff0c;标记为 1 到 N。 给定一个列表 times&#xff0c;其中 times[i] (u, v, w) 表示有一条从节点 u 到节点 v 的时延为 w 的有向边。 现在&#xf…...

25、架构-微服务的驱动力

微服务架构的驱动力可以从多方面探讨&#xff0c;包括灵活性、独立部署、技术异构性、团队效率和系统弹性等。 灵活性和可维护性 灵活性是微服务架构的一个主要优势。通过将单体应用拆分成多个独立的微服务&#xff0c;开发团队可以更容易地管理、维护和更新各个服务。每个微…...

JeecgFlow事件网关概念及案例

事件网关 通常网关基于连线条件决定后续路径&#xff0c;但事件网关有所不同&#xff0c;其基于事件决定后续路径。事件网关的每条外出顺序流都需要连接一个捕获中间事件。 事件网关只有分支行为&#xff0c;流程的走向完全由中间事件决定。可以从多条候选分支中选择事件最先达…...

使用鸿蒙HarmonyOs NEXT 开发 快速开发 简单的购物车页面

目录 资源准备&#xff1a;需要准备三张照片&#xff1a;商品图、向下图标、金钱图标 1.显示效果&#xff1a; 2.源码&#xff1a; 资源准备&#xff1a;需要准备三张照片&#xff1a;商品图、向下图标、金钱图标 1.显示效果&#xff1a; 定义了一个购物车页面的布局&#x…...

iOS 中 attribute((constructor)) 修饰的函数

开发环境声明&#xff1a;此文描述的 attribute((constructor)) 特指使用 Objective-C 开发 iOS、MacOS&#xff0c;Swift 语言不支持这种属性修饰符。 初识 attribute((constructor)) 在 Objective-C 开发中&#xff0c;attribute((constructor)) 是一个 GCC 和 Clang 编译器…...

原生js实现图片预览控件,支持丝滑拖拽,滚轮放缩,放缩聚焦

手撸源代码如下&#xff1a;注释应该很详细了&#xff0c;拿去直用 可以放到在线编辑器测试&#xff0c;记得修改图片路径 菜鸟教程在线编辑器 <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" conten…...

C语言入门课程学习笔记9:指针

C语言入门课程学习笔记9 第41课 - 指针&#xff1a;一种特殊的变量实验-指针的使用小结 第42课 - 深入理解指针与地址实验-指针的类型实验实验小结 第43课 - 指针与数组&#xff08;上&#xff09;实验小结 第44课 - 指针与数组&#xff08;下&#xff09;实验实验小结 第45课 …...

借助 Cloudflare D1 和 Drizzle 在 Astro 上实现全栈

使用 Cloudflare D1 和 Drizzle ORM 将后端添加到 Astro 项目的分步指南 文章目录 安装 Astro添加 Cloudflare 适配器部署到 Pages安装 wrangler 并登录创建 D1 数据库创建 wrangler.toml 文件将 .wrangler 添加到 .gitignore更新 astro.config.ts安装 Drizzle 依赖项创建 driz…...

SUSE linux 15的网络管理

1 手工配置网络 wicked提供了一种新的网络配置框架。自SUSE 12起&#xff0c;SUSE使用了新的网络管理工具wicked&#xff0c;这个是区别与其他常见发行版的。常见的发行版目前大多使用的是NetworkManager服务进行网络管理。 1.1 wicked网络配置 传统网络接口管理面临的挑战之…...

海康威视-下载的录像视频浏览器播放问题

目录 1、播放异常比对 2、视频编码检查 2.1、正常视频解析 2.2、海康视频解析 2.3、比对工具 3、转码 3.1、maven依赖 3.2、实现代码 4、验证 在前面的文章&#xff08;海康威视-按时间下载录像文件_海康威视 sdk 下载录像 大小0-CSDN博客&#xff09;中&#xff0c;通…...

养殖自动化管理系统:开启智慧养殖新篇章

在现代农业的快速演进中&#xff0c;养殖业正经历一场前所未有的技术革命。养殖自动化管理系统&#xff0c;作为这场变革的前沿科技&#xff0c;正逐步成为推动行业高效、环保、可持续发展的关键力量。本文将深入探讨自动化养殖系统如何通过精准管理、智能监控、数据驱动决策&a…...

SmartEDA革新来袭:融合Multisim与Proteus精髓,引领电子设计新纪元!

在电子设计领域&#xff0c;每一次技术的革新都如同春风化雨&#xff0c;滋润着设计师们的心田。今天&#xff0c;我们迎来了一个划时代的电子设计自动化&#xff08;EDA&#xff09;工具——SmartEDA&#xff0c;它不仅融合了业界知名的Multisim和Proteus的精华&#xff0c;更…...

【FFmpeg】AVFormatContext结构体

【FFmpeg】AVFormatContext结构体 1.AVFormatContext结构体1.2 const struct AVInputFormat *iformat1.3 const struct AVOutputFormat *oformat 参考&#xff1a; FFMPEG结构体分析&#xff1a;AVFormatContext 示例工程&#xff1a; 【FFmpeg】调用ffmpeg库实现264软编 【FF…...

【SpringSecurity】认证与鉴权框架SpringSecurity——授权

目录 权限系统的必要性常见的权限管理框架SpringSecurity授权基本流程准备脚本限制访问资源所需权限菜单实体类和Mapper封装权限信息封装认证/鉴权失败处理认证失败封装鉴权失败封装配置SpringSecurity 过滤器跨域处理接口添加鉴权hasAuthority/hasAnyAuthorityhasRole/​ hasA…...

深入解析FTP:原理、架构与搭建方式

在当今互联网世界中&#xff0c;文件传输是日常工作和生活中不可或缺的一部分。FTP&#xff08;File Transfer Protocol&#xff0c;文件传输协议&#xff09;作为一种老而弥坚的协议&#xff0c;一直在文件传输领域发挥着重要作用。本文将从技术人的角度&#xff0c;详细分析F…...

Springboot与RestTemplate

RestTemplate是Spring提供的用于访问Rest服务的客户端&#xff0c;RestTemplate提供了多种便捷访问远程Http服务的方法,能够大大提高客户端的编写效率。 一、使用Get进行访问 1、获取json格式 使用 getForEntity() API 发起 GET 请求&#xff1a; RestTemplate restTemplate…...

端口发布与暴露

端口发布与暴露 目录 发布端口发布到临时端口发布所有端口试一试 使用 Docker CLI使用 Docker Compose 如果你一直在跟随本指南&#xff0c;你应该理解容器为应用程序的每个组件提供了隔离的进程。每个组件 - 如 React 前端、Python API 和 Postgres 数据库 - 都运行在自己的…...

Unity:使用Texture2D动态创建的图像无法正常显示 / 修改图像后未生效

开发中遇到需要动态绘制图像的需求&#xff0c;前后文代码如下所示&#xff1a; Texture2D newImageTexture new Texture2D(width, height); Color32[] newImagePixels new Color32[height * width];for (int y 0; y < height ; y) {for (int x 0; x < width; x){if…...

【LinuxC语言】详解TCP/IP

文章目录 前言TCP与UDP协议的介绍TCP协议流式传输TCP的三次握手连接TCP的四次挥手连接断开总结前言 在我们的日常生活中,无论是浏览网页,还是发送电子邮件,甚至是在线视频聊天,都离不开网络通信。而在网络通信中,TCP和UDP协议起着至关重要的作用。本文将以通俗易懂的语言…...

数字化转型下的企业人力资源信息系统研究

随着数字化转型的加速&#xff0c;企业人力资源管理面临着全新的挑战和机遇。传统的人力资源信息系统&#xff08;HRIS&#xff09;在新时代的要求下必须进行深刻的革新和升级&#xff0c;以更好地支持企业的发展战略和员工的需求。 数据驱动的决策支持 在当今这个信息化迅猛发…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...