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

代码随想录算法训练营第六十三天| 图论9—卡码网47. 参加科学大会，94. 城市间货物运输 I

news 来源：原创 2025/7/14 8:13:15

每日被新算法方式轰炸的一天，今天是dijkstra（堆优化版）以及Bellman_ford ，尝试理解中，属于是只能照着代码大概说一下在干嘛。

47. 参加科学大会

https://kamacoder.com/problempage.php?pid=1047

dijkstra（堆优化版），主要区别用gpt总结了一下

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

其中核心部分主要是最小堆来从当前所有候选路径中找出距离起点最近的节点，更新它所连接的其他节点的最短路径值。从堆里取出当前距离起点最近的节点，并尝试用它来更新所有邻接点的距离，直到终点被访问或堆为空。也就是中间while函数的意义，其余代码主要是构建堆以及处理输入。

import heapqclass Edge:def __init__(self, to, val):self.to = toself.val = valdef dijkstra(n, m, edges, start, end):grid = [[] for _ in range(n + 1)]for p1, p2, val in edges:grid[p1].append(Edge(p2, val))minDist = [float('inf')] * (n + 1)visited = [False] * (n + 1)pq = []heapq.heappush(pq, (0, start))minDist[start] = 0while pq:cur_dist, cur_node = heapq.heappop(pq)if visited[cur_node]:continuevisited[cur_node] = Truefor edge in grid[cur_node]:if not visited[edge.to] and cur_dist + edge.val < minDist[edge.to]:minDist[edge.to] = cur_dist + edge.valheapq.heappush(pq, (minDist[edge.to], edge.to))return -1 if minDist[end] == float('inf') else minDist[end]# 输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
start = 1  # 起点
end = n    # 终点# 运行算法并输出结果
result = dijkstra(n, m, edges, start, end)
print(result)

94. 城市间货物运输 I

https://kamacoder.com/problempage.php?pid=1152

最主要区别在于Bellman_ford能解决负数的权重的问题，而dijkstra不行，

Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

然后是该算法的核心思想：松弛操作

外层循环最多执行 n-1 次（这是 Bellman-Ford 的核心步骤）
每次遍历所有边，尝试更新目标点的最短距离（即“松弛”操作）
如果一轮下来没有任何更新，说明最短路径已稳定，提前退出循环（优化）

def main():n, m = map(int, input().strip().split())edges = []for _ in range(m):src, dest, weight = map(int, input().strip().split())edges.append([src, dest, weight])minDist = [float("inf")] * (n + 1)minDist[1] = 0  # 起点处距离为0for i in range(1, n):updated = Falsefor src, dest, weight in edges:if minDist[src] != float("inf") and minDist[src] + weight < minDist[dest]:minDist[dest] = minDist[src] + weightupdated = Trueif not updated:  # 若边不再更新，即停止回圈breakif minDist[-1] == float("inf"):  # 返还终点权重return "unconnected"return minDist[-1]if __name__ == "__main__":print(main())

代码随想录算法训练营第六十三天| 图论9—卡码网47. 参加科学大会，94. 城市间货物运输 I

每日被新算法方式轰炸的一天，今天是dijkstra（堆优化版）以及Bellman_ford ，尝试理解中，属于是只能照着代码大概说一下在干嘛。 47. 参加科学大会 https://kamacoder.com/problempage.php?pid1047 dijkstra&#xff08…...

编程日记 2025/7/14 8:13:15

RAG之大规模解析 PDF 文档全流程实战

PDF 文档在商业、学术和政府领域无处不在，蕴含着大量宝贵信息。然而，从 PDF 中提取结构化数据却面临着独特的挑战，尤其是在处理数千甚至数百万个文档时。本指南探讨了大规模解析 PDF 的策略和工具。 PDF解析挑战 PDF 的设计初衷是为了提供一致的视觉呈现，而非数据提取。这…...

编程日记 2025/6/28 23:06:02

uart16550详细说明

一、介绍 uart16550 ip core异步串行通信IP连接高性能的微控制器总线AXI,并为异步串行通信提供了控制接口。软核设计连接了axilite接口。二、特性 1.axilite接口用于寄存器访问和数据传输 2.16650串口和16450串口的软件和硬件寄存器都是兼容的 3.默认的core配置参数&#xf…...

编程日记 2025/7/14 7:53:53

Docker 环境安装（2025最新版）

Docker在主流的操作系统和云平台上都可以使用，包括Linux操作系统（如Ubuntu、 Debian、Rocky、Redhat等）、MacOS操作系统和 Windows操作系统，以及AWS等云平台。 Docker官网： https://docs.docker.com/ 配置宿主机网…...

编程日记 2025/7/14 6:58:01

Comparator不满足自反性错误，Comparison method violates its general contract

APP运行退出，跟踪信息 java.lang.IllegalArgumentException: Comparison method violates its general contract! Collections.sort(idxsList);//按score升序排列查看idxs类 public int compareTo(Idxs o) { //重写compareTo方法 return (int) (this.g…...

编程日记 2025/7/14 7:09:01

[Java实战]Spring Boot 3 整合 Apache Shiro（二十一）

[Java实战]Spring Boot 3 整合 Apache Shiro（二十一） 引言在复杂的业务系统中，安全控制（认证、授权、加密）是核心需求。相比于 Spring Security 的重量级设计，Apache Shiro 凭借其简洁的 API 和灵活的扩…...

编程日记 2025/7/14 7:51:41

如何界定合法收集数据？

首席数据官高鹏律师团队在当今数字化时代，数据的价值日益凸显，而合法收集数据成为了企业、机构以及各类组织必须严守的关键准则。作为律师，深入理解并准确界定合法收集数据的范畴，对于保障各方权益、维护法律秩序至关重要。一…...

编程日记 2025/6/29 18:59:41

Flask+HTML+Jquery 文件上传下载

HTML 代码： <div id"loadingIndicator" style"display:none;"><div class"spinner"></div> </div>  <form action"" method"post" enctype"m…...

编程日记 2025/6/28 23:53:37

MapReduce打包运行

（一）maven打包 MapReduce是一个分布式运算程序的编程框架，是用户开发“基于Hadoop的数据分析应用”的核心框架。 MapReduce核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序（例如：jar…...

编程日记 2025/7/14 6:55:04

国产化Word处理控件Spire.Doc教程：如何使用 C# 从 Word 中提取图片

通过编程方式从 Word 文档中提取图片，可以用于自动化文档处理任务。E-iceblue旗下Spire系列产品是国产文档处理领域的优秀产品，支持国产化，帮助企业高效构建文档处理的应用程序。本文将演示如何使用 C# 和 Spire.Doc for .NET 库从 Word 文件…...

编程日记 2025/7/14 7:38:59

07 mysql之DQL

一、什么是DQL DQL 是 SQL 的一部分，专门用于查询数据。核心命令是 SELECT，是最常用的命令，支持：简单查询条件过滤排序与分页多表连接聚合统计子查询与复杂逻辑二、基础查询语法 SELECT 字段1, 字段2, ... FROM 表名 WHERE 条件表达式 GROUP BY 分组字段 HAVING 分组条件…...

编程日记 2025/7/14 6:33:25

spark-standalone

一、定义：Standalone 模式是一种独立的集群部署模式，自带完整服务，可单独部署到一个集群中，无需依赖任何其他资源管理系统。二、配置步骤 1.和前面一样拉到hadoop101的/opt/module这个目录里面。 2.压缩 3.重命名为spark-sta…...

编程日记 2025/6/29 0:34:29

运行Spark程序-在shell中运行 --SparkConf 和 SparkContext

SparkConf 类用于配置 Spark 应用程序的各种参数。通过 SparkConf 类，你可以设置应用程序的名称、运行模式（如本地模式、集群模式）、资源分配（如内存、CPU 核心数）等。主要作用配置应用程序参数：可以设置 S…...

编程日记 2025/6/28 23:06:00

分割任务 - 数据增强

语义分割 - FCN ： 数据预处理/数据增强算法源码实例 base_size520 crop_size480 flip_prob0.5if train_val train:self.transforms transforms.Compose([transforms.RandomResize(int(base_size*0.5), int(base_size*2)),transforms.RandomHorizontalFlip(flip_…...

编程日记 2025/7/11 15:34:19

基于C#+MySQL实现（WinForm）企业设备使用信息管理系统

企业设备使用信息管理系统引言企业的设备管理在企业的生产制造和管理过程之中意义比较重大，明确企业的设备的产权和维护成本对于企业的成本控制和财务管理之中起到了重要的作用。随着市场竞争的加剧，现代企业所处的市场环境发生了深刻的变革&#xf…...

编程日记 2025/6/29 1:07:58

JavaScript异步编程 Async/Await 使用详解：从原理到最佳实践

🌷 古之立大事者，不惟有超世之才，亦必有坚忍不拔之志 🎐 个人CSND主页——Micro麦可乐的博客 🐥《Docker实操教程》专栏以最新的Centos版本为基础进行Docker实操教程，入门到实战 🌺《RabbitMQ》…...

编程日记 2025/7/14 6:54:20

Babylon.js学习之路《四、Babylon.js 中的相机（Camera）与视角控制》

文章目录 1. 引言：为什么相机是 3D 场景的“眼睛”？1.1 相机的核心作用1.2 常见相机类型概览 2. 相机基础参数解析2.1 通用属性2.2 相机坐标系 3. 详解常用相机类型3.1 自由相机（FreeCamera）3.2 弧形旋转相机（ArcRotat…...

编程日记 2025/7/14 7:25:45

MCP Server多节点滚动升级一致性治理

飞书云文档原链接地址：https://ik3te1knhq.feishu.cn/wiki/W8ctwG2sAiPkrXkpl7ocP0g0njf [!TIP] MCP Server 多节点部署时，滚动发布，MCP Client 侧使用的 Client 连接保证使用的是最新的工具配置信息后续推进：按比例使用旧、新实…...

编程日记 2025/7/14 7:16:26

多线程（二）

今天先来了解一个上一期的遗留概念 —— 前台线程与后台线程一 . 前台线程与后台线程大家应该多多少少都听过酒桌文化，咱们平常吃饭，座位次序是没有那么多讲究的，但是在跟领导吃饭，或者出席宴会和一些重要场所的饭局时&#…...

编程日记 2025/7/14 7:00:04

2025年，大模型LLM还有哪些可研究的方向？

近两年LLM在学术界与工业界的发展大家都有目共睹。到了今年，以预训练LLM为代表的大模型PK上半场已然结束，接下来就要进入下半场大模型2.0时代了。那么在这新赛道，关于大模型我们还有什么可做的创新？要知道，如今的大模…...

编程日记 2025/7/14 7:57:39

VS打断点调试，无法命中断点或断点失效，解决方法

1.打开需要打断点的模块，点击属性，将C/C常规的调试信息格式改为程序数据库（/Zi） 2.将C/C的优化禁用（/Od） 3.将链接器中的生成调试信息改为生成调试信息（/DEBUG） 注：如果需…...

编程日记 2025/7/14 4:42:34

ELF文件详解

ELF 文件不仅仅是一个格式，它是 Linux 世界中程序的"灵魂容器"，承载着程序从编译到执行的整个生命周期。今天咱们来聊一个看起来高深，实际上理解起来其实挺简单的话题—— ELF 文件。不知道你有没有想过：我们敲下./…...

编程日记 2025/6/29 1:16:46

【学习笔记】Shell编程---流程控制语句

最近学了好多个流程控制语句，都有点混乱了，赶紧先把各种用法记录下来！ if 语句语法格式： if 条件测试命令串 then 条件为真时执行的命令 else 条件为假时执行的命令 fi 以关键字if开头，后跟条件测试表达式&…...

编程日记 2025/7/8 12:31:13

TensorFlow 常见使用场景及开源项目实例

TensorFlow 常见使用场景及开源项目实例摘要本文详细介绍了 TensorFlow 在多个领域的典型应用及其对应的开源项目案例。涵盖了图像处理、自然语言处理、语音音频处理、推荐系统与时间序列预测、移动端与边缘计算以及生成式模型与创意应用等多方面内容，列举了大量…...

编程日记 2025/7/9 15:45:54

王炸组合！STL-VMD二次分解 + Informer-LSTM 并行预测模型

往期精彩内容： 单步预测-风速预测模型代码全家桶-CSDN博客半天入门！锂电池剩余寿命预测（Python）-CSDN博客超强预测模型：二次分解-组合预测-CSDN博客 VMD CEEMDAN 二次分解，BiLSTM-Attention预测模型…...

编程日记 2025/6/29 0:52:46

OpenCV进阶操作：风格迁移以及DNN模块解析

文章目录前言一、风格迁移1、风格迁移是什么？2、步骤1）训练2）迁移二、DNN模块1、什么是DNN模块2、DNN模块特点3、流程图4、图像预处理功能三、案例实现1、数据预处理2、加载模型总结前言风格迁移（Style Transfer&#xff0…...

编程日记 2025/6/28 23:27:12

使用bitNet架构

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言一、配置二、报错总结前言大型语言模型（LLM）面临的挑战：高能耗、高内存需求、部署门槛高。微软提出 BitNet 架构&#x…...

编程日记 2025/6/28 23:06:05

OpenCV中的光流估计方法详解

文章目录一、引言二、核心算法原理1. 光流法基本概念2. 算法实现步骤三、代码实现详解1. 初始化设置2. 特征点检测3. 光流计算与轨迹绘制四、实际应用效果五、优化方向六、结语一、引言在计算机视觉领域，运动目标跟踪是一个重要的研究方向，广泛应用…...

编程日记 2025/6/28 23:39:32

Java集合框架详解与使用场景示例

Java集合框架是Java标准库中一组用于存储和操作数据的接口和类。它提供了多种数据结构，每种数据结构都有其特定的用途和性能特点。在本文中，我们将详细介绍Java集合框架的主要组成部分：List、Set和Queue，并通过代码示例展示它们的…...

编程日记 2025/6/29 0:05:32

多模态融合【十九】——MRFS: Mutually Reinforcing Image Fusion and Segmentation

目录一.摘要二.Introduction 三. 背景与动机四.方法 4.1. 概述 4.2. IGM-Att模块 4.3. PC-Att模块 4.4. 任务头五.实验 5.1. 数据集与实现细节 5.2. 语义分割 5.3. 图像融合 5.4. 消融研究 5.5. IGM-Att和PC-Att的应用增益 5.6. 复杂度讨论 5.7. 目标检测的…...

编程日记 2025/6/29 0:42:45

音频转文字-在线工具包及使用记录

资料来源：https://zhuanlan.zhihu.com/p/269603431（多种方案） 视频教程：https://www.youtube.com/watch?vL1H5ov4WTBg https://github.com/openai/whisper // 创建虚拟环境 python -m venv myvnev// 激活虚拟环境 source myvne…...

编程日记 2025/6/29 0:52:58

集合-进阶

Collection collection的遍历方式迭代器遍历不依赖索引 import java.util.ArrayList; import java.util.Collection; import java.util.Iterator;public class mycollection {public static void main(String[] args) {//1.创建集合并添加元素Collection<String> co…...

编程日记 2025/6/29 0:01:58

【阿里云】阿里云 Ubuntu 服务器无法更新 systemd（Operation not permitted）的解决方法

零、前言目前正在使用的Ubuntu服务器中，仅阿里云（不止一台）出现了这个问题，因此我判定是阿里云服务器独有的问题。如果你的服务器提供商不是阿里云，那么这篇文章可能对你没有帮助。如果已经因为升级错误导致依赖冲突…...

编程日记 2025/7/2 10:29:29

wpf DataGrid 行选择命令绑定

在WPF中实现DataGrid行选择与命令绑定的MVVM模式，可通过以下方式结合代码示例实现： 1. ‌基础绑定与命令触发（SelectionChanged事件绑定）‌ 通过Interaction.Triggers捕获SelectionChanged事件，并绑定到ViewModel中的命令： <DataGrid ItemsSource="{Binding I…...

编程日记 2025/6/28 23:06:10

【认知思维】验证性偏差：认知陷阱的识别与克服

什么是验证性偏差验证性偏差（Confirmation Bias）是人类认知中最普遍、最根深蒂固的心理现象之一，指的是人们倾向于寻找、解释、偏爱和回忆那些能够确认自己已有信念或假设的信息，同时忽视或贬低与之相矛盾的证据。这种认知偏差影…...

编程日记 2025/7/11 5:53:32

大容量存储的高性能 T-BOX 方案对智能网联汽车的支撑

在智能网联汽车快速发展的当下，车载 T-BOX（Telematics Box）作为车辆与云端互联的核心枢纽，其性能和可靠性直接决定了用户体验的上限。米客方德（MK）推出的基于 STM32H7RX 主控芯片与 MKDV4GIL-AST&#xff0…...

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

Linux 内核网络协议栈：从 Socket 类型到协议注册的深度解析

Linux 内核的网络协议栈是一个复杂而高效的体系，涉及多层次的协议处理与数据流转。本文通过分析核心数据结构（如 inetsw 数组、sock_type 枚举）和关键函数（如 inet_add_protocol），深入探讨其工作原理与设计哲学。一、Socket 类型与 sock_type 枚举 1.1 Socket 类型的定…...

编程日记 2025/6/28 23:06:11

vim,gcc/g++,makefile,cmake

一、vim：你的小帮手——文本编辑器它是干嘛的？ 想象你的代码就像是写在一本“程序的笔记本”里，vim就是一个超级厉害的“数字笔记本”或“文字编辑器”。它有什么用？ 编写代码：编辑、修改你的源代码代码高亮&…...

编程日记 2025/6/28 23:10:34

解决 CentOS 7 镜像源无法访问的问题

在国内使用 CentOS 系统时，经常会遇到镜像源无法访问或者下载速度慢的问题。尤其是默认的 CentOS 镜像源通常是国外的，如果你的网络环境无法直接访问国外服务器，就会出现无法下载包的情况。本文将介绍如何修改 CentOS 7 的镜像源为国内镜像源…...

编程日记 2025/7/13 13:58:43

“傅里叶变换算法”来检测货物外形损坏

“傅里叶变换算法”来检测货物外形损坏要使用傅里叶变换算法来检测货物外形损坏，首先需要理解基本概念。傅里叶变换是一种数学变换，用于将信号从时域（或空间域）转换到频域。在图像处理中，二维傅里叶变换可以用来分析…...

编程日记 2025/7/9 23:07:39

python打卡day24

可迭代对象、OS模块知识点回顾： 元组可迭代对象os模块作业：对自己电脑的不同文件夹利用今天学到的知识操作下，理解下os路径 1.元组在day3的打卡内容中就介绍了元组，跟列表比起来就是用了圆括号，有序可以重复&#x…...

编程日记 2025/6/29 0:42:27

MapReduce 入门实战：WordCount 程序

一、引言在大数据处理领域，MapReduce 是一种开创性的编程模型和处理框架，它使得我们能够高效地在大规模分布式系统上处理海量数据。而 WordCount 程序作为 MapReduce 的经典入门案例，堪称大数据领域的 “Hello World”，帮助无数…...

编程日记 2025/6/29 0:40:02

深度剖析：Vue2 项目兼容第三方库模块格式的终极解决方案

当我们为 Vue2 项目引入某些现代 JavaScript 库时，常常会遇到这样的报错： error in ./node_modules/some-lib/lib/index.mjs Cant import the named export xxx from non EcmaScript module这类问题的本质是模块格式的世纪之争 —— ES Module&#xff…...

编程日记 2025/7/11 15:56:07

5.11作业

拓扑图： 需求分析： 要求五台路由器的环回地址均可以相互访问配置： r1 int g 0/0/0 i…...

编程日记 2025/6/28 23:06:12

MyBatis 批量新增与删除功能完整教程

一、功能概述通过 MyBatis 动态 SQL 实现以下功能：批量新增：一次性插入多条员工记录，支持自增主键回填。批量删除：根据 ID 数组一次性删除多条记录。二、代码逐行解析 1. Mapper 接口定义 // 批量新增：传入员工对象集合 void insertAll(List<Emp> empList);// …...

编程日记 2025/6/29 0:55:11

Spark，RDD中的行动算子

RDD中的行动算子 collect算子格式：def collect(): Array[T] 参数说明：该算子没有参数。并以数组的形式返回统计个数 reduce算子格式：def reduce(func: (T, T) > T): T 返回值：返回一个单一的值，其类型与…...

编程日记 2025/6/29 0:58:04

Linux：进程控制2

一：进程程序替换 1. 一旦程序替换成功，就去执行新代码了，原始代码的后半部分已经不存在了 2. exec*系列的函数，没有成功返回值，只有失败返回值-1 在程序替换的过程中，并没有创建新的进程，只是…...

编程日记 2025/6/28 23:53:59

Java jar包程序启动停止脚本 shell bash

启动启动时可指定前缀（名称） start.sh #!/bin/bash # 使用时直接运行# 寻找当前目录下后缀为 .jar 的文件 #options($(find . -maxdepth 1 -type f -name "*.jar")) # 寻找当前目录下后缀为 .jar 的文件，并按时间倒序排序 opt…...

编程日记 2025/7/4 18:15:10

【Linux】进程通信管道

🌻个人主页：路飞雪吖~ 🌠专栏：Linux 目录一、👑进程间通信分类二、👑管道 🌟什么是管道？ 🌟匿名管道 🎉原理： 🔥站在文件描述…...

编程日记 2025/6/29 0:48:06

基于智能家居项目解析DHT11温湿度传感器

一、模块简介 DHT11 是一款数字式温湿度传感器，内部集成了温度传感元件、湿度传感元件以及一个 8 位单片机芯片，用于采集数据和通信。。测量范围：湿度 20%～90% RH，温度 0～50℃ 精度：湿度 5% …...

编程日记 2025/6/28 23:45:13

47. 参加科学大会

94. 城市间货物运输 I

相关文章：