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

[leetcode]3123. 最短路径中的边(Dijkstra+反向搜索找边)

news 来源：原创 2025/9/2 7:45:27

题目链接

题意

给定n个点的无向图
给定一个edges={u,v,w}数组表示u到v有一条边权为w的无向边
返回一个bool数组ans，ans[i]=1表示edges[i]在任意一条0到n-1的最短路中

思路

先Dijkstra找出最短路
再从n-1出发反向搜索当前点i，邻接点j，边权w
如果dis[j]==dis[i]+w 说明这条边在最短路上

Code

using ll = long long;
#define pii pair<ll,int>
#define ar3 array<ll,3>
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;class Solution {
public:vector<bool> findAnswer(int n, vector<vector<int>>& edges) {int m=edges.size();vector<vector<ar3>>g(n);// vector<vector<int>>mp(n,vector<int>(n,-1));for(int i=0;i<m;i++){auto e=edges[i];int u=e[0],v=e[1],w=e[2];// mp[u][v]=mp[v][u]=i;g[u].push_back({w,v,i});g[v].push_back({w,u,i});}priority_queue<pii,vector<pii>,greater<>>pq;pq.emplace(0,0);vector<ll>dis(n,LINF);dis[0]=0;while(pq.size()){auto [d,i]=pq.top();pq.pop();if(d>dis[i]) continue;for(auto [w,j,_]:g[i]){ll nd=d+w;if(nd<dis[j]){dis[j]=nd;pq.emplace(nd,j);}}}if(dis[n-1]==LINF) {return vector<bool>(m,false);}vector<bool>st(n);st[n-1]=1;vector<bool>ans(m);function<void(int)>dfs=[&](int i){for(auto [d,j,id]:g[i]){if(dis[j]+d==dis[i]){ans[id]=1;if(st[j]==0){st[j]=1;dfs(j);}}}};dfs(n-1);return ans;}
};

实现细节

注意要把边的编号存在g里面不能像注释里一样另外存编号会MLE

[leetcode]3123. 最短路径中的边(Dijkstra+反向搜索找边)

题目链接题意给定n个点的无向图给定一个edges{u,v,w}数组表示u到v有一条边权为w的无向边返回一个bool数组ans，ans[i]1表示edges[i]在任意一条0到n-1的最短路中思路先Dijkstra找出最短路再从n-1出发反向搜索当前点i，邻接点j，边权…...

编程日记 2025/9/2 7:45:27

构建macOS命令速查手册：基于Flask的轻量级Web应用实践

构建macOS命令速查手册：基于Flask的轻量级Web应用实践一、项目概述本文介绍一个基于Flask框架开发的macOS命令速查Web应用。该应用通过结构化的命令数据存储和响应式前端设计，为用户提供便捷的命令查询体验，具备以下特点： 六…...

编程日记 2025/8/28 8:22:43

中国移动启动数字乡村“五新升级”：年底前，行政村5G覆盖达95%

大湾区经济网品牌观察报道，近日，在国家全面推进乡村振兴的战略背景下，中国移动近日发布数字乡村升级行动计划，以“AI大模型数智化平台”为核心引擎，围绕“五新升级”构建“两个新型”信息服务体系。一、数字基建筑基&…...

编程日记 2025/8/18 0:40:32

借助mcpo在open-webui中使用mcp

open-webui前几天发布了0.6版本，我立即进行了升级。新版本中一个重要功能是通过mcpo方式支持了mcp server。本文将介绍mcpo是什么，以及如何在open-webui中使用它。同时，我也会分享几个在接入过程中遇到的问题及解决方案。首先来介绍mcpo&…...

编程日记 2025/8/30 19:18:30

Mysql的备份还原

MySQL日志日志类型 MySQL有几个不同的日志文件，可以帮助你找出mysqld内部发生的事情： 日志文件记入文件中的信息类型错误日志记录启动、运行或停止时出现的问题。查询日志记录建立的客户端连接和执行的语句。二进制日志记录所有更改数据的语句。主要用…...

编程日记 2025/9/2 7:44:21

测试：正交法设计测试用例

目录一、什么是正交法二、利用正交表设计测试用例正交法设计测试用例的步骤一、什么是正交法正交法的目的是为了减少测试用例的数量，让尽可能少的用例覆盖两两组合。认识正交表。最简单的正交表是L4(2^3)，含意如下： “L”代表正…...

编程日记 2025/9/2 7:38:33

zk基础—5.Curator的使用与剖析一

大纲 1.基于Curator进行基本的zk数据操作 2.基于Curator实现集群元数据管理 3.基于Curator实现HA主备自动切换 4.基于Curator实现Leader选举 5.基于Curator实现分布式Barrier 6.基于Curator实现分布式计数器 7.基于Curator实现zk的节点和子节点监听机制 8.基于Curator创…...

编程日记 2025/9/2 7:39:40

VSCode中结合DeepSeek使用Cline插件的感受

前言听网上有传言说AI智能插件Cline非常的好用，而且相对Cursor而言还是免费的，捆绑的大模型选择也比较的广泛。所以，特意安装试用了一下。我的采用IDE是VSCode，捆绑的大模型是最近比较火的DeepSeek。总体使用下来感觉非常的棒。…...

编程日记 2025/9/2 7:42:16

安卓开发工程师-Java 常用数据结构

1. Java 中的数组和集合有什么区别？ 数组： 长度固定：一旦声明，长度不能改变。类型单一：只能存储相同类型的元素。存储效率高：底层是连续的内存空间，访问速度快。示例代码： int[] …...

编程日记 2025/9/2 7:39:41

thinkphp8.0上传图片到阿里云对象存储(oss)

1、开通oss,并获取accessKeyId、accessKeySecret <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><tit…...

编程日记 2025/9/2 7:38:36

Angular 2 模板语法详解

Angular 2 模板语法详解引言 Angular 2 作为一款强大的前端框架，以其组件化的开发模式和高效的性能被众多开发者所青睐。模板语法是Angular 2中用于定义组件UI的关键部分。本文将详细介绍Angular 2的模板语法，帮助开发者更好地理解和运用这一功能。模板语法概述 Angula…...

编程日记 2025/9/1 11:17:14

进行性核上性麻痹护理攻略：多维度守护健康

日常起居护理保证患者居住环境安全，清除地面障碍物，避免患者跌倒。家具摆放固定且合理，方便患者活动。为患者准备宽松、舒适、易于穿脱的衣物，减轻穿衣时的困难。在饮食上，提供富含营养、易于吞咽的食物，…...

编程日记 2025/9/1 9:59:19

MessageQueue --- RabbitMQ WorkQueue

MessageQueue --- RabbitMQ WorkQueue 什么是WorkQueue如何分发RoundRobinFair dispatch (Prefetch) --- 能者多劳什么是WorkQueue Work queues，任务模型。简单来说就是让多个消费者绑定到一个队列，共同消费队列中的消息。当消息处理比较耗时的时候&…...

编程日记 2025/9/2 7:39:42

Redis内存碎片详解！

目录一、什么是内存碎片？🤔二、为什么 Redis 会有内存碎片呢？🤷‍♀️三、如何查看 Redis 内存碎片的信息？🔍四、如何清理 Redis 内存碎片？🧹五、总结📝 &#x1f3…...

编程日记 2025/9/2 7:39:41

如何使用 Nginx 代理 Easysearch 服务

Nginx 是一个高性能的 HTTP 服务器和反向代理服务器，广泛用于负载均衡、缓存、SSL 终端和服务代理等场景。本篇将尝试使用 Nginx 代理 Easysearch 服务，方法同样适用于 Elasticsearch 和 Opensearch。测试环境 Easysearch 集群版本为 1.10.0&#xff…...

编程日记 2025/8/23 20:04:08

用python输出OLED字模库的符号

提示：博主是小白，如有不足，望海涵和指出在单片机上练习使用OLED显示屏时，可以看到有个OLED字模库本文用python将这些字符打印出来，代码如下（本文只适用与128*64的OLED，如果是其它OLED&#xf…...

编程日记 2025/8/27 10:46:57

【java】Class.newInstance()

在 Java 中，Class.newInstance()是一个用于创建类的新实例的方法。它调用类的无参构造函数来创建对象。然而，从 Java 9 开始，Class.newInstance()方法已经被标记为废弃，推荐使用其他替代方法。 Class.newInstance()的使用 Class.…...

编程日记 2025/9/1 9:07:31

下述操作参考 Building Arrow C — Apache Arrow v20.0.0.dev267 安装依赖组件 sudo apt-get install \build-essential \ninja-build \cmake 下载源码 git clone --recursive --shallow-submodules gitgithub.com:apache/arrow.git 配置创建build目录并且进入 mkdir a…...

编程日记 2025/8/31 4:17:15

第二届图像处理与人工智能国际学术会议（ICIPAI2025）

重要信息时间：2025年4月18日-20日地点：吉林-长春（线上线下结合） 官网：www.icipai.org 简介（部分） 主题其他图像处理与人工智能（Image Processing & Artificial Intell…...

编程日记 2025/8/28 8:30:09

Kafka 消息堆积的原因有哪些？

Kafka 产生消息堆积的本质原因是： ⚠️ “消费速度 < 生产速度”，也就是：写入太快，处理太慢。下面我从实际场景出发，帮你梳理出常见的几种堆积情况，结合原因和例子，便于你对号入座排查问题 …...

编程日记 2025/8/27 18:00:41

解决cline等免费使用deepseek模型的问题

OpenAI、OpenRouter、Claude等都无法在国内免费正常使用，cline作为在vscode中应对cursor比较好的替代方案，怎么使用免费Deepseek，最核心的是在点击模型名称打开配置以下几项： 1、打开VSCode左侧的Cline\Roo Cline插件面板 2、点…...

编程日记 2025/8/31 13:44:10

ROS多设备交互

ROS多设备连接同一个Master：ROS Master多设备连接-CSDN博客在多个PC端连接同一个ROS Master后，接下来就可以实现不同设备之间的话题交流，Master主机端启动不同PC端的功能包等功能了尽管多个PC端拥有不同的ROS工作空间，但是只要…...

编程日记 2025/8/25 0:49:35

浅谈 MVVM 模式

MVVM（Model-View-ViewModel） 是一种软件架构设计模式，旨在将用户界面（UI）与业务逻辑分离，从而提高代码的可维护性和可测试性。它在现代前端开发和桌面应用开发中得到了广泛应用，尤其是在构建复杂…...

编程日记 2025/8/29 11:50:17

flutter点击事件教程

在 Flutter 中，处理点击事件是非常常见的操作。Flutter 提供了多种方式来实现用户交互，比如按钮点击、手势检测等。下面是一个详细的教程，帮助你理解如何在 Flutter 中实现点击事件。一、使用 onPressed 实现按钮点击事件 Flutter 提供了 E…...

编程日记 2025/8/28 11:24:59

[SAP SD] 常用事务码

在SAP系统中，事务码(Transaction Code)是一个具有特定功能的代码标识符，用于快速调用和执行SAP系统内的各种业务模块的功能 /NT-code: 关闭当前业务窗口，退回到SAP初始界面，进入对应的T-Code窗口 /OT-code: 新建SAP GUI窗口&…...

编程日记 2025/8/27 4:58:58

【＜二＞丹方改良：Spring 时代的 JavaWeb】之 Spring Boot 的未来：从微服务到云原生的演进

<前文回顾> 点击此处查看合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、引子&…...

编程日记 2025/8/30 0:53:38

保留格式地一键翻译英文ppt

我手头上有一个贝叶斯推断的英文ppt，假如我想翻译成中文，整合起来进行pre，你会怎么做？ 1，复制粘贴型： 在翻译软件与源文件ppt之间不断流转，效率太低 2，office ppt自带翻译插入整合…...

编程日记 2025/8/31 15:20:43

晶晨S905L3S／S905L3SB_安卓9.0_10秒开机_通刷-线刷固件包

晶晨S905L3S／S905L3SB_安卓9.0_10秒开机_通刷-线刷固件包线刷方法：（新手参考借鉴一下） 使用晶晨刷机工具USB_Burning_Tool进行刷机；请使用Amlogic USB Burning Tool v2.2.5或v2.2.7（晶晨线刷烧录工具v2.2…...

编程日记 2025/9/1 1:22:11

Android Transition转场动效使用全解析

Transition的使用和原理项目效果 1. 简述 Android 4.4.2 中引入了 Transition 过渡动画，不过功能比较简单。在 Android 5.0 的 Material Design 中引入更完整和强大的 Transition 框架。通过Transition可以实现： 同一个页面中的场景过渡动画Activit…...

编程日记 2025/9/2 3:27:20

第九章Python语言高阶加强-面向对象篇

目录一.初始对象二.成员方法 1.成员变量和成员方法三.类和对象四.构造方法五.其他内置方法（魔术方法） 1.__str__字符串方法 2.__lt__小于符号比较方法 3.__le__小于等于比较符号方法 4.__eq__比较运算符实现方法六.封装七.继承 1.继承…...

编程日记 2025/8/25 21:43:57

AI重构SEO关键词智能布局

内容概要随着人工智能技术在搜索引擎优化领域的深入发展，AI驱动的关键词智能布局正在重塑传统SEO策略的核心逻辑。通过整合自然语言处理、深度学习与语义分析技术，现代SEO系统已形成包含智能分词、意图解码、动态优化的三维技术框架，使关键…...

编程日记 2025/9/1 3:21:43

言同数字：法新社AFP海外新闻媒体发稿成功案例——出海品牌背书必备

作者：言同数字全球传播团队一、品牌困境：当中国技术遇上海外认知壁垒案例背景： 某中国光伏储能企业（应保密要求匿名，代号"GreenTech"），其家用储能系统在欧洲市场遭遇&#xff1…...

编程日记 2025/8/28 17:08:42

第三章 react redux的学习之redux和react-redux，@reduxjs/toolkit依赖结合使用

redux系列文章目录第一章简单学习redux,单个reducer 第二章简单学习redux,多个reducer 第四章 react-redux，reduxjs/toolkit依赖，学习第五章两张图告诉你redux常使用的api有哪些前言前面两章，我们是只使用的redux的依赖。本章…...

编程日记 2025/8/29 0:56:55

【HTML】纯前端网页小游戏-戳破彩泡

分享一个简单有趣的网页小游戏 - 彩色泡泡爆破。玩家需要点击屏幕上随机出现的彩色泡泡来得分。 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wi…...

编程日记 2025/9/2 1:12:38

【Python使用】嘿马云课堂web完整实战项目第3篇：增加数据,修改数据【附代码文档】

教程总体简介：项目概述项目背景项目的功能构架项目的技术架构 CMS 什么是CMS CMS需求分析与工程搭建静态门户工程搭建 SSI服务端包含技术页面预览开发 4 添加“页面预览”链接页面发布需求分析技术方案测试环境搭建数据字典服务端前端数据模型页面原…...

编程日记 2025/8/29 3:53:02

数据结构【栈和队列附顺序表应用算法】

栈和队列和顺序表应用算法练习 1.栈1.1概念与结构1.2栈的实现 2.队列2.1概念与结构2.2队列的实现 3.附（顺序表应用算法）3.1移除元素3.2删除有序数组中的重复项3.3合并两个有序数组 1.栈 1.1概念与结构栈：⼀种特殊的线性表，其只…...

编程日记 2025/8/28 6:04:49

Redis数据结构之String

目录 1.概述2.常见操作2.1 SET/GET2.2 MSET/MGET/MSETNX2.3 GETRANGE/SETRANGE2.4 INCR(BY)/DECR(BY)2.5 STRLEN2.6 APPEND2.7 GETSET 3.小结 1.概述 String是最常用的数据类型，一个key对应一个value。String是二进制安全的，可以包含任何数据&#xff0…...

编程日记 2025/8/18 0:20:31

Maven 远程仓库推送方法

步骤 1：配置 pom.xml 中的远程仓库地址在项目的 pom.xml 文件中添加 distributionManagement 配置，指定远程仓库的 URL。 xml 复制 <project>...<distributionManagement><snapshotRepository><id…...

编程日记 2025/8/31 11:05:33

uname

在 C 语言中，uname 函数用于获取当前操作系统的相关信息。它是 POSIX 标准的一部分，定义在 <sys/utsname.h> 头文件中。通过调用 uname 函数，可以获取系统名称、节点名称（主机名）、操作系统版本、机器硬件架构…...

编程日记 2025/8/27 1:06:17

【无标题】object，wait，notifyAll

在 Java 中，Object类提供了wait()方法，用于线程间的协作和同步。wait()方法使得当前线程暂停执行，并释放当前对象的锁，直到其他线程调用该对象的notify()或notifyAll()方法将其唤醒。这是实现线程间通信和同步的重要机制之一。 w…...

编程日记 2025/9/1 9:07:42

【Vue】核心特性实战解析：computed、watch、条件渲染与列表渲染

目录一、计算属性（computed） ✅ 示例： 计算属性-methods实现：在插值模块里，实现函数的调用功能计算属性-computed的实现： 计算属性-简写： ✅ 特点： ⚠️ 与 methods 的区别…...

编程日记 2025/8/29 17:52:40

精品可编辑PPT | 基于湖仓一体构建数据中台架构大数据湖数据仓库一体化中台解决方案

本文介绍了基于湖仓一体构建数据中台架构的技术创新与实践。它详细阐述了数据湖、数据仓库和数据中台的概念，分析了三者的区别与协作关系，指出数据湖可存储大规模结构化和非结构化数据，数据仓库用于高效存储和快速查询以支持决策，…...

编程日记 2025/8/28 0:19:33

基于Python网络爬虫的智能音乐可视化系统(源码+lw+部署文档+讲解)，源码可白嫖!

摘要时代在飞速进步，每个行业都在努力发展现在先进技术，通过这些先进的技术来提高自己的水平和优势，智能音乐可视化系统当然不能排除在外。我本次开发的基于网络爬虫的智能音乐可视化系统是在实际应用和软件工程的开发原理之上，…...

编程日记 2025/9/2 0:39:01

基于STM32与应变片的协作机械臂力反馈控制系统设计与实现----2.2 机械臂控制系统硬件架构设计

2.2 机械臂控制系统硬件架构设计一、总体架构拓扑 1.1 典型三级硬件架构 #mermaid-svg-MWmxD3zX6bu4iFCv {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-MWmxD3zX6bu4iFCv .error-icon{fill:#552222;}#mermaid-s…...

编程日记 2025/8/30 14:07:16

在线记事本——支持Markdown

项目地址 https://github.com/Anyuersuper/CloudNotebook 百度网盘通过网盘分享的文件：CloudNotebook-master.zip 链接: https://pan.baidu.com/s/1kd2qNvm0eXc6_7oYDR769A?pwdyuer 提取码: yuer 📝 云笔记 (Cloud Notebook) 云笔记是一个简洁、安全…...

编程日记 2025/9/1 15:57:46

DDPM 做了什么

本博客主要侧重点在于HOW也就是DDPM怎么做的而不是WHY为什么要这样做那么第一个问题DDPM做了一件什么事：这个算法通过逐渐向原图像添加噪声来破坏图像，然后再学习如何从噪声成恢复图像。第二件事如何做到的：通过训练一个网络，…...

编程日记 2025/8/30 18:23:17

Redis数据结构之List

目录 1.概述2.常见操作2.1 LPUSH/RPUSH/LRANGE2.2 LPOP/RPOP2.3 LINDEX2.4 LLEN2.5 LREM2.6 LTRIM2.7 RPOPLPUSH2.8 LSET2.9 LINSERT 1.概述 List是简单的字符串列表，单key多个value，按照插入顺序排序。支持添加一个元素到列表的头部(左边)或者尾部(右…...

编程日记 2025/8/28 6:56:54

L2-023 图着色问题 #DFS C++邻接矩阵存图

文章目录题目解读输入格式输出格式思路Ac CODE 参考题目解读给定一个无向图V，询问是否可以用K种颜色为V中每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色输入格式第一行给出V,E,K， 分别代表无向图的顶点，…...

编程日记 2025/8/27 15:05:42

架构下的按钮效果设置

以下是一个完整的跨QML/Qt Widgets的主题方案实现，包含对按钮阴影的统一管理： 一、项目结构 Project/ ├── core/ │ ├── thememanager.h │ └── thememanager.cpp ├── widgets/ │ ├── mainwindow.h │ ├── mainwindow.cpp …...

编程日记 2025/8/28 22:10:29

Unhandled exception: org.apache.poi.openxml4j.exceptions.InvalidFormatException

代码在main方法里面没有报错，在Controller里面就报错了。原来Controller类里面少了行代码 import org.apache.poi.openxml4j.exceptions.InvalidFormatException; 加上去就解决了。...

编程日记 2025/8/18 0:40:29

题意

思路

Code

实现细节

相关文章：