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

【Day50 LeetCode】图论问题 Ⅷ

news 来源：原创 2025/9/13 21:30:05

一、图论问题 Ⅷ

1、dijkstra算法堆优化

采用堆来优化，适合节点多的稀疏图。代码如下：

# include<iostream>
# include<vector>
# include<list>
# include<queue>
# include<climits>using namespace std;class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};int main(){int n, m;cin >> n >> m;int s, e, v;vector<list<pair<int, int>>> grid(n+1);for(int i=0; i<m; ++i){cin >> s >> e >> v;grid[s].push_back(pair<int, int>(e, v));}vector<int> minDist(n+1, INT_MAX);vector<bool> visited(n+1, false);int start = 1, end = n;minDist[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;pq.push(pair<int, int>(start, 0));while(!pq.empty()){// 1、选取源点到未被访问过且距离最近的节点； auto cur = pq.top(); pq.pop();if(visited[cur.first])continue;// 2、将最近节点标记为访问过 visited[cur.first] = true;// 3、更新非访问节点到源点的距离for(auto edge : grid[cur.first]){if(!visited[edge.first] && minDist[edge.first] > minDist[cur.first] + edge.second )minDist[edge.first] = minDist[cur.first] + edge.second;pq.push(pair<int, int>(edge.first, minDist[edge.first]));}}if(minDist[end] < INT_MAX)cout << minDist[end] << endl;elsecout << -1 << endl;return 0;
}

2、Bellman_ford 算法

权值有负值的图无法采用dijdijkstra算法，这时需要使用Bellman_ford 算法来解决最短路问题。

#include <iostream>
#include <vector>
#include <list>
#include <climits>using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid.push_back({p1, p2, val});}int start = 1, end = n;  vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛int from = side[0]; // 边的出发点int to = side[1]; // 边的到达点int price = side[2]; // 边的权值// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX)cout << "unconnected" << endl; // 不能到达终点elsecout << minDist[end] << endl; // 到达终点最短路径return 0;
}

参考资料
代码随想录

【Day50 LeetCode】图论问题 Ⅷ

一、图论问题 Ⅷ 1、dijkstra算法堆优化采用堆来优化，适合节点多的稀疏图。代码如下： # include<iostream> # include<vector> # include<list> # include<queue> # include<climits>using namespace std;class myco…...

编程日记 2025/9/13 21:30:05

人大金仓KCA | 用户与角色

人大金仓KCA | 用户与角色一、知识预备1. 用户和角色二、具体实施1. 用户管理-命令行1.1 创建和修改用户1.2 修改用户密码1.3 修改用户的并发连接数1.4 修改用户的密码有效期 2.用户管理-EasyKStudio2.1 创建和修改用户2.2 修改用户密码2.3 修改用户的并发连接数2.4 修改用户…...

编程日记 2025/9/13 21:29:24

嵌入式开发：傅里叶变换（4）：在 STM32上面实现FFT（基于STM32L071KZT6 HAL库+DSP库）

目录步骤 1：准备工作步骤 2：创建 Keil 项目，并配置工程步骤 3：在MDK工程上添加 CMSIS-DSP 库步骤 5：编写代码步骤 6：配置时钟和优化步骤 7：调试与验证步骤 8：优化和调…...

编程日记 2025/9/12 23:06:15

【AI学习从零至壹】Numpy基础知识

PyTorch基础知识 Numpy基础NumPy 基本数据类型Numpy数组 NumPy 基础数组创建Numpy特殊数组创建Numpy数组的访问NumPy数组的遍历Numpy数组的常用属性比较常用的属性有： Numpy数组的基本操作Numpy数组的数学操作加减乘除 Numpy线性代数Numpy广播机制 Numpy基础 NumPy…...

编程日记 2025/9/13 21:28:22

Day11，Hot100（贪心算法）

贪心 （1）121. 买卖股票的最佳时机第 i 天卖出的最大利润，即在前面最低价的时候买入 class Solution:def maxProfit(self, prices: List[int]) -> int:min_price prices[0]ans 0for price in prices:ans max(ans, price - min_price…...

编程日记 2025/9/13 21:28:22

Transformer 代码剖析1 - 数据处理（pytorch实现）

引言 Transformer 架构自《Attention Is All You Need》论文发表以来，在自然语言处理领域引起了巨大的变革。它摒弃了传统的循环结构，完全基于注意力机制，显著提高了处理序列数据的效率和性能。本文将通过对一个具体的项目代码结构进行详细分…...

编程日记 2025/9/13 21:30:05

Python--模块（下）

3. 内置模块 3.1 os模块常用功能： os.mkdir("new_dir") # 创建目录 os.listdir(".") # 列出当前目录文件 os.path.join("dir", "file.txt") # 路径拼接 os.path.abspath(__file…...

编程日记 2025/9/13 12:42:12

Android Studio超级详细讲解下载、安装配置教程（建议收藏）

博主介绍：✌专注于前后端、机器学习、人工智能应用领域开发的优质创作者、秉着互联网精神开源贡献精神，答疑解惑、坚持优质作品共享。本人是掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战，深受全网粉丝喜爱与支持✌有…...

编程日记 2025/9/13 21:27:18

PS画笔工具

画笔工具： 画笔工具（B）（原理：单位笔刷的连续填充，文件格式.abr）：圆形矢量笔刷、动态矢量画笔（旧版画笔里有与压感笔有关）、图案填充画笔 shift画笔&#xff…...

编程日记 2025/9/13 21:27:19

[Java基础] JVM常量池介绍（BeanUtils.copyProperties(source, target)中的属性值引用的是同一个对象吗）

文章目录 1. JVM内存模型2. 常量池中有什么类型？3. 常量池中真正存储的内容是什么4. 判断一个字符串(引用)是否在常量池中5. BeanUtils.copyProperties(source, target)中的属性值引用的是同一个对象吗？6. 获取堆内存使用情况、非堆内存使用情况 1. JVM内…...

编程日记 2025/9/13 21:23:53

1.68M 免安装多格式图片批量转 webp 无广告软件推荐

软件介绍今天要给大家分享一款超实用的图片处理工具，它能实现多格式图片向 webp 格式的转换，无论是 jpg、png、tif、gif 还是 webp 格式自身的图片，都能批量且借助多线程技术进行转换。直接打开就能用，体积小巧，仅 …...

编程日记 2025/9/13 21:27:19

LeetCode 1472.设计浏览器历史记录：一个数组完成模拟，单次操作均O(1)

【LetMeFly】1472.设计浏览器历史记录：一个数组完成模拟，单次操作均O(1) 力扣题目链接：https://leetcode.cn/problems/design-browser-history/ 你有一个只支持单个标签页的浏览器 ，最开始你浏览的网页是 homepage &#xff0c…...

编程日记 2025/9/12 7:11:40

[笔记.AI]AI知识科普提纲

仅供参考 1.AI基础认知 1.1什么是什么AI 1.2核心概念 1.2.1机器学习、深度学习、神经网络 1.2.2模型：模型、大模型、模型参数 1.2.3多模态 1.2.4生成式AI & 判别式AI 1.3发展与现状 2.大模型 2.1主流大模型 2.1.1分类 2.1.2各…...

编程日记 2025/9/13 21:24:56

学习知识的心理和方法杂记-01

前言： 1 学习新知识要讲究方法，“知识未学方法先行”，写本系列文章是为了给自己加深大脑“条件反射”的，因为我自己学习新知识的过程中老会被不科学的“杂念”干扰，导致学习效率低下。 2 关于天才和普通人&#xff…...

编程日记 2025/9/13 21:28:21

网页制作10-html,css,javascript初认识の适用XHTML

一、简介： Xhtml是extensible hypertext markup language的缩写。它是由国际W3C组织制定并公布发行的。是一个过渡技术，结合了部分xml的强大功能及大多数html的简单特性。 Advantage. Xhtml提倡更简洁规范的代码。 Xhtml.文档在旧的基于的浏览器中&…...

编程日记 2025/9/13 21:26:39

C++ 中 cin 和 cout 教程

一、概述在 C 里，cin 和 cout 是标准库 <iostream> 中用于输入输出操作的重要对象，它们基于流的概念，为开发者提供了方便且类型安全的输入输出方式。cin 是标准输入流对象，主要用于从标准输入设备（一般是键盘&…...

编程日记 2025/9/13 21:28:21

Qt for Android下QMessageBox背景黑色、文字点击闪烁

最近在基于Qt开发安卓应用的时候，在红米平板上默认QMessageBox出现之后，背景黑色，并且点击提示文字会出现闪烁，影响用户体验。问题分析 1、设置QMessageBox样式，设置背景色、文字颜色，如下所示： QMessageBox {background: white;color: white; } 尝试之后，问题仍存…...

编程日记 2025/9/13 21:26:40

C++20的指定初始化器（Designated Initializers）

文章目录指定初始化器的使用条件语法嵌套结构体的初始化数组的指定初始化注意事项优势 C20引入了**指定初始化器（Designated Initializers）**这一特性，允许在初始化结构体、联合体或类的对象时，明确指定成员变量的初始化值&#…...

编程日记 2025/9/8 4:31:00

Windows 11【1001问】删除Win11左下角小组件的6种方法

在Windows 11中，左下角的小组件功能虽然提供了天气、新闻等实用信息，但对于一些用户来说可能显得多余或干扰视线。因此，微软提供了多种方式让用户能够自定义是否显示这些小组件。以下是 6 种常见的设置方法来隐藏或关闭Windows 11左下角的小组…...

编程日记 2025/9/9 12:36:23

kotlin的函数标准库使用

摘要说明函数标准库常用的有： 1、apply： apply函数作为一个配置函数，可以传入一个接收者，然后调用一系列函数来配置它以方便使用，如果提供lambda给apply函数执行，它会返回配置好的接收者使用介绍&#x…...

编程日记 2025/9/8 6:24:47

深入剖析：自定义实现C语言中的atoi函数

在C语言的标准库中， atoi 函数是一个非常实用的工具，它能够将字符串形式的数字转换为对应的整数。然而，当我们深入探究其实现原理时，会发现其中蕴含着许多有趣的编程技巧和细节。本文将详细讲解如何自定义实现一个类似 atoi 功能的…...

编程日记 2025/9/12 17:38:22

Kubernetes (K8S) 核心原理深度剖析：从架构设计到运行机制

Kubernetes（K8S）作为容器编排领域的“操作系统”，其设计和实现原理是开发者进阶的必修课。本文将从架构设计、核心组件协作、关键机制实现三个维度，结合源码逻辑与实战场景，分享 K8S 的底层运行原理。一、Kubernetes 架构设计 1. 声明式 API 与控制器模式 K8S 的核心设…...

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

springboot做接口限流

目录 1. 依赖全局配置2. 注解配置 1. 依赖全局配置引入依赖 <dependency><groupId>com.github.taptap</groupId><artifactId>ratelimiter-spring-boot-starter</artifactId><version>1.2</version></dependency>appl…...

编程日记 2025/9/8 21:41:04

Visual Studio Code 跨平台安装与配置指南（附官方下载链接）

一、软件定位与核心功能 Visual Studio Code（简称VS Code）是微软开发的开源跨平台代码编辑器，支持超过50种编程语言的智能补全、调试和版本控制功能。2025版本新增AI辅助编程模块，可自动生成单元测试代码和API文档注释。二、下载…...

编程日记 2025/9/9 21:16:21

TaskBuilder设置排序条件

在整个向导的最后一步，可以设置是否按指定字段的值对查询结果进行排序，支持正序和倒序两种排序方式。如果没有设置任何排序字段，则默认按数据库里现有数据记录的实际存储的先后顺序排序。如果设置了多个排序条件，则按这些条件从上…...

编程日记 2025/9/10 3:55:29

挖src实用脚本开发(二)

文章目录技术原理代码实现一代码实现二总结这篇文章记录cms识别脚本。技术原理 1.使用在线平台识别，比如whatcms，fofa等 2.自己写脚本识别，但是指纹库麻烦，需要耗费大量精力代码实现一这里我使用的是whatcms接口&#xff0…...

编程日记 2025/9/8 22:54:23

[ISP] AE 自动曝光

相机通过不同曝光参数（档位快门时间 x 感光度 x 光圈大小）控制进光量来完成恰当的曝光。自动曝光流程大概分为三部分： 1. 测光：点测光、中心测光、全局测光等；通过调整曝光档位使sensor曝光在合理的阈值内&#xff0…...

编程日记 2025/9/9 1:49:38

DeepSeek-R1：通过强化学习激发大语言模型的推理能力

注：此文章内容均节选自充电了么创始人，CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》（人工智能科学与技术丛书）【陈敬雷编著】【清华大学出版社】文章目录 DeepSeek大模型技术系列三DeepSeek大模型技术系列三》DeepSeek-…...

编程日记 2025/9/12 22:26:31

docker search rocketmq#拉取镜像 docker pull foxiswho/rocketmq:server-4.3.2 docker pull foxiswho/rocketmq:broker-4.3.2 #创建nameserver容器 docker create -p 9876:9876 --name rmqserver \ -e "JAVA_OPT_EXT-server -Xms128m -Xmx128m -Xmn128m" \ -e "…...

编程日记 2025/9/9 1:49:38

算法训练（leetcode）二刷第三十七天 | 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

刷题记录 *300. 最长递增子序列674. 最长连续递增序列基础解法（非动规）动态规划 718. 最长重复子数组滚动数组 *300. 最长递增子序列 leetcode题目地址 dp数组含义： dp[i]表示以nums[i]结尾的最长递增子序列长度，即以nums[i]结尾…...

编程日记 2025/9/10 18:55:08

LSTM长短期记忆网络-原理分析

1 简介概念 LSTM（Long Short-Term Memory）也称为长短期记忆网络，是一种改进的循环神经网络（RNN），专门设计用于解决传统RNN的梯度消失问题和长程依赖问题。LSTM通过引入门机制和细胞状态，能够更…...

编程日记 2025/8/16 13:01:14

Java 面试题 20250227

Java 中序列化与反序列化是什么？ 序列化：将 Java 对象转化成可传输的字节序列格式（字节流、JSON、XML），以便于传输和存储。反序列化：将字节序列格式数据转化成 Java 对象的过程。 1、为什么需要序列化和…...

编程日记 2025/9/9 19:42:08

Spring事务失效六大场景

引言 Spring事务一般我们采用注解实现，但是我们构造事务实现的时候常常没察觉失效的情况，本篇文章总结事务失效的六大情况，帮助我们深刻理解事务失效的边界概念 1. 方法自调用这个主要是针对声明式事务的，经过前面的介绍&…...

编程日记 2025/9/13 11:38:29

C++和OpenGL实现3D游戏编程【连载23】——几何着色器和法线可视化

欢迎来到zhooyu的C++和OpenGL游戏专栏，专栏连载的所有精彩内容目录详见下边链接： 🔥C++和OpenGL实现3D游戏编程【总览】 1、本节实现的内容上一节课，我们在Blend软件中导出经纬球模型时，遇到了经纬球法线导致我们在游戏中模型光照显示问题，我们在Blender软件中可以通过…...

编程日记 2025/9/8 20:05:12

Python游戏编程之赛车游戏6-2

3.2 move()方法的定义 Player类的move()方法用于玩家控制汽车左右移动，当玩家点击键盘上的左右按键时，汽车会相应地进行左右移动。 move()方法的代码如图7所示。图7 move()方法的代码其中，第20行代码通过pygame.key.get_pressed()函数获…...

编程日记 2025/9/10 16:54:41

Vxe UI 根据vxe-tabs 绑定不同的值，渲染生成不同的 tabls（页签）内容

VxeUI tabs控件，根据绑定不同的内容，动态渲染不同的表格数据放置在不同的 tab 页效果图如下： 代码实现 <template><vxe-tabs :options"detailTabList"><vxe-tab-pane v-for"(item, index) in detailTabList&…...

编程日记 2025/9/9 3:47:43

Element Plus中el-select选择器的下拉选项列表的样式设置

el-select选择器，默认样式效果： 通过 * { margin: 0; padding: 0; } 去掉内外边距后的样式效果（样式变丑了）： 通过 popper-class 自定义类名修改下拉选项列表样式 el-select 标签设置 popper-class"custom-se…...

编程日记 2025/9/12 22:52:14

YOLOv11-ultralytics-8.3.67部分代码阅读笔记-train.py

train.py ultralytics\models\yolo\detect\train.py 目录 train.py 1.所需的库和模块 2.class DetectionTrainer(BaseTrainer): 1.所需的库和模块 # Ultralytics 🚀 AGPL-3.0 License - https://ultralytics.com/licenseimport math import random from copy…...

编程日记 2025/9/10 15:17:21

PR 安装包 2018-2024（Win，Mac）文中为使用技巧和教程

下载链接：https://pan.baidu.com/s/1LLv1tSXJxUcv6iOlcAHJEg?pwd1234 导语：Adobe Premiere Pro以98%的行业覆盖率和跨平台协作能力，稳居2025年视频剪辑工具榜首。本文涵盖基础配置、核心剪辑、高级调色、效率革命、企业级实战五大模块&…...

编程日记 2025/9/8 4:31:03

请求Geoserver的WTMS服务返回200不返回图片问题-跨域导致

今天碰到个奇怪问题，改了个页面标题再打包布署GeoServer发现调用WTMS服务失败，请求返回状态码200，返回包大小0，使用postman模拟请求是可以正常返回图片的。跟之前版本对比如下： 正常Response请求: HTTP/1.1 200X-Fr…...

编程日记 2025/9/13 1:58:23

TCP基本入门-简单认识一下什么是TCP

部分内容来源：小林Coding TCP的特点 1.面向连接一定是“一对一”才能连接，不能像 UDP 协议可以一个主机同时向多个主机发送消息，也就是一对多是无法做到的 2.可靠的无论的网络链路中出现了怎样的链路变化，TCP 都可以保证一个…...

编程日记 2025/9/10 0:33:38

计算机科学技术领域的内卷现状与应对措施分析

计算机科学技术领域的内卷现状与应对措施分析李升伟整理 ### 计算机科学技术领域的内卷现状与应对措施分析 #### 一、内卷现状分析 1. **教育与升学内卷** 计算机科学与技术相关专业（如计算机科学与技术、人工智能、大数据等）已成为考研竞争最…...

编程日记 2025/9/7 22:03:16

The First项目报告：VANA如何重塑数据所有权与AI训练

在当今的数字化时代，数据已成为比黄金更为珍贵的资源。科技巨头们通过收集和分析用户的个人数据，获得巨大的商业利益，而用户却往往没有从中得到应有的回报。这种数据的不对等交易和隐私侵犯现象，成为了现代社会的一个严重问题。 …...

编程日记 2025/9/11 13:38:06

pnpm的基本用法

以下是 pnpm 的核心命令和使用指南，涵盖从安装依赖到项目管理的常见操作： 1. 基础命令 (1) 安装依赖 pnpm install # 安装 package.json 中的所有依赖 pnpm install <包名> # 安装指定包（自动添加到 dependencies&#xf…...

编程日记 2025/9/11 19:42:01

机试刷题_从上往下打印二叉树【python】

从上往下打印二叉树 # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # param root …...

编程日记 2025/9/13 12:42:05

转化率(漏斗分析)——mysql计算过程

转化率(漏斗分析)——mysql计算过程问题：有一张表，记录了不同用户的用户id，浏览页面时间，加入购物车时间，下单时间，支付时间，算出每天的各个环节的转化率创建表info(含用户id，浏…...

编程日记 2025/9/9 3:05:40

《AI和人工智能和编程日报》

OpenAI：将深度研究扩展到 ChatGPT Plus、Team、Edu 和 Enterprise 用户，每月 10 次查询；Pro 用户每月有 120 次查询，ChatGPT 语音模式向免费用户开放。DeepSeek：R1 大模型宣布降价，调用价格将至四分之一&am…...

编程日记 2025/9/13 9:01:51

自然语言处理：稀疏向量表示

介绍大家好，我是博主。今天又来和大家分享自然语言处理领域的知识了。原本我计划这次分享NLP中文本表示的相关内容，不过在整理分享计划的过程中，发现这部分知识里包含一些涉及复杂数学原理和抽象概念的内容。对于刚接触NLP的小伙伴们来说&a…...

编程日记 2025/9/7 19:09:35

矩阵 trick 系列题解

1.AT_dp_r Walk（矩阵图论） 题意一个有向图有 n n n 个节点，编号 1 1 1 至 n n n。给出一个二维数组 A 1... n , 1... n A_{1...n,1...n} A1...n,1...n，若 A i , j 1 A_{i,j}1 Ai,j1 说明节点 i i i 到节点 j j j …...

编程日记 2025/9/9 3:18:47

视频字幕识别和翻译

下载的视频很多不是汉语的，我们需要用剪映将语音识别出来作为字幕压制到视频中去。剪映6.0以后语音识别需要收费，但是低版本还是没有问题。如果想要非汉语字幕转成中文，剪映低版本不提供这样功能。但是，用剪映导出识别字幕&am…...

编程日记 2025/9/2 12:26:00

一、图论问题 Ⅷ

1、dijkstra算法 堆优化

2、Bellman_ford 算法

相关文章：

1、dijkstra算法堆优化