代码随想录算法训练营第六十一天|Bellman_ford 队列优化算法(又名SPFA)、bellman_ford之判断负权回路
卡码网:94. 城市间货物运输 I
from collections import dequeclass Edge:def __init__(self, to, val):self.to = to # 链接的节点self.val = val # 边的权重def main():n, m = map(int, input().split())grid = [list() for _ in range(n + 1)] # 初始化邻接表for _ in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val)) # p1 指向 p2,权值为 valstart = 1 # 起点end = n # 终点min_dist = [float('inf')] * (n + 1) # 存储从起点到每个节点的最短距离min_dist[start] = 0que = deque([start]) # 使用双端队列存储已访问节点is_in_queue = [False] * (n + 1) # 标记是否在队列中while que:node = que.popleft()is_in_queue[node] = False # 从队列中移除节点for edge in grid[node]:to = edge.tovalue = edge.valif min_dist[to] > min_dist[node] + value: # 开始松弛min_dist[to] = min_dist[node] + valueif not is_in_queue[to]: # 如果节点不在队列中,则加入队列que.append(to)is_in_queue[to] = Trueif min_dist[end] == float('inf'):print("unconnected") # 不能到达终点else:print(min_dist[end]) # 打印到达终点的最短路径长度if __name__ == "__main__":main()
卡码网:95. 城市间货物运输 II
from collections import dequeclass Edge:def __init__(self, to, val):self.to = to # 链接的节点self.val = val # 边的权重def main():n, m = map(int, input().split())grid = [list() for _ in range(n + 1)] # 邻接表# 将所有边保存起来for _ in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val)) # p1 指向 p2,权值为 valstart = 1 # 起点end = n # 终点min_dist = [float('inf')] * (n + 1) # 存储从起点到每个节点的最短距离min_dist[start] = 0que = deque([start]) # 使用双端队列存储已访问节点count = [0] * (n + 1) # 记录节点加入队列几次count[start] = 1flag = Falsewhile que:node = que.popleft()for edge in grid[node]:to = edge.tovalue = edge.valif min_dist[to] > min_dist[node] + value: # 开始松弛min_dist[to] = min_dist[node] + valueque.append(to)count[to] += 1if count[to] == n: # 如果加入队列次数超过 n-1次 就说明该图与负权回路flag = Truebreakif flag:breakif flag:print("circle")elif min_dist[end] == float('inf'):print("unconnected")else:print(min_dist[end])if __name__ == "__main__":main()
相关文章:
代码随想录算法训练营第六十一天|Bellman_ford 队列优化算法(又名SPFA)、bellman_ford之判断负权回路
卡码网:94. 城市间货物运输 I from collections import dequeclass Edge:def __init__(self, to, val):self.to to # 链接的节点self.val val # 边的权重def main():n, m map(int, input().split())grid [list() for _ in range(n 1)] # 初始化邻接表for _…...
ArrayList集合源码解读(二)已完结
ArrayList集合源码解读(二) 前言 这篇文章已经把 ArrayList 更完了。各位还想看什么源码可以私信我~~ 上节课带大家阅读了 ArrayList 中的核心扩容代码,那么今天带大家阅读下List集合中我们常用的几个方法的底层实现逻辑! 常用…...
光伏逆变器、MPPT、PCS储能变流器、BMU、BCU、BDU和液冷机组
一、光伏逆变器 光伏逆变器(PV inverter或solar inverter)可以将光伏(PV)太阳能板产生的可变直流电压转换为市电频率交流电(AC)的逆变器,可以反馈回商用输电系统,或是供离网的电网使…...
OpenHarmony编译
简介:本文将会介绍编译OpendHarmony环境的搭建、编译、和刷机(rk3568) 使用场景:修改系统源码,需要验证修改的功能是否正确、编译镜像、编译SDK 1、VS Code,下载链接,用于修改源码 2、linux环…...
C语言典型例题30
《C程序设计教程(第四版)——谭浩强》 习题2.7 从银行贷了一笔款d,准备每月还款额为p,月利率为r,计算多少个月能还清。 设d30000元,p6000元,r1%。对求得的月份取小数点后一位,对第二…...
springMVC @RestControllerAdvice注解使用方式
使用 RestControllerAdvice 的主要场景包括: 全局异常处理:处理所有控制器中抛出的未捕获异常。数据校验失败处理:处理 Bean Validation 校验失败的情况。自定义响应:统一定义响应格式或错误信息。 RestControllerAdvice 注解的…...
HarmonyOS鸿蒙开发岗位面试中关于组件的问题总结
文章目录 1. 鸿蒙组件的基本概念2. 组件的使用3. 布局管理4. 组件间通信5. 组件化开发6. 性能优化7. 实战应用 鸿蒙应用开发岗位面试中关于鸿蒙组件的问题,通常会涉及多个关键知识点,这些知识点涵盖了鸿蒙组件的基本概念、使用、布局管理、性能优化、组件…...
Unity 在Editor下保存对Text组件的文本的修改
Unity 在Editor下保存对Text组件的文本的修改 /****************************************************文件:TimeStampForText.cs作者:lenovo邮箱: 日期:2024/8/8 1:9:21功能: *************************************************…...
mysql 日志爆满,删除日志文件,定时清理日志
今天发现网站不能正常访问,于是登陆服务器查找问题。 机智的我随手用命令:df -l 发现 硬盘爆满了,于是就知道问题所在了。 Filesystem 1K-blocks Used Available Use% Mounted on/dev/xvda1 20641404 16963004 16929876 10…...
MySQL学习(19):锁
1.什么是锁 锁是计算机协调多个进程或线程并发访问某一资源的机制。 在数据库中,数据是供许多用户共享的资源,数据库必须保证数据并发访问的一致性、有效性,这就要靠锁来协调实现。 MySOL中的锁,分为以下三类: &am…...
【出海日记】关于 KD ,数据工具的陷阱
一个关键词:deepwoken builder 对标的竞品:deepwoken.co 初步分析: https://ahrefs.com/keyword-difficulty/?countryus 显示这个关键词优化难度极低 拿流量的是一个内页,单靠这个内页一个月有 22 万的流量 看起来很香&#x…...
【k8s集群部署篇】在openEuler环境下部署多master高可用kubernetes集群详细教程(V1.30版本)
【k8s集群部署篇】在openEuler环境下部署多master高可用kubernetes集群详细教程(V1.30版本) 一、相关名词介绍1.1 k8s简介1.2 Keepalived简介1.3 HAProxy简介二、本次实践介绍2.1 环境规划介绍2.2 本次实践简介三、所有节点基础环境配置3.1 主机配置工作3.2 关闭防火墙和seli…...
数据结构:链表经典算法OJ题
目录 前言 一、移除链表元素 二、反转链表 三、合并两个有序链表 四、链表的中间节点 五、环形链表的约瑟夫问题 前言 在了解了链表的相关知识后,我们还需要一些题目进行练习加深对链表这方面知识的理解,也可以用来检测链表这块学的的怎么样&#…...
【线性代数】【二】2.2 极大线性无关组与向量空间的基
文章目录 前言一、极大线性无关组二、向量空间的基三、向量维数与向量空间维数总结 前言 上一篇中我们介绍了向量空间的概念,并且学习了对任意给出的一组向量,如果构造一个向量空间。本文将更加细致的去分析张成一个向量空间,具有哪些性质。…...
OD C卷 - CPU算力分配
CPU算力分配 两组服务器A、B, 每组有多个算力不同的CPU;为了让两组服务器的算力和相等,允许两组各选出一个CPU进行一次交换;求两组中用于交换的CPU算力,从A中选出的算力尽可能小; 输入描述: 第一行 输入L…...
matlab实现红绿灯识别
在MATLAB中实现红绿灯识别通常涉及图像处理技术,包括颜色分割、形态学操作、边缘检测等步骤。下面我将给出一个基本的框架和示例代码,用于在MATLAB中识别图像中的红绿灯。 步骤 1: 读取图像 首先,你需要有一张包含红绿灯的图像。 img imr…...
base64 转 pdf
工作中经常会遇到一些签名的pdf传输,一般都是base64编码,这样就需要我们手动转为pdf, 其实根本不需要自己使用pdf的库写入,只是数据的简单写入就行 package mainimport ("encoding/base64""fmt""os&quo…...
vue2项目微信小程序的tabs切换效果
在 Vue 2 项目中实现类似微信小程序的 tabs 切换效果,可以通过 Vue 的 router-view 和 <router-link> 来完成。这里我们使用 Vue Router 来创建一个标签页切换的效果。 步骤 1: 安装 Vue Router 如果还没有安装 Vue Router,首先需要安装它&#…...
WPF动画的使用
前言 弹幕是什么?这里是使用动画将控件弹起来,通过C#提供的多样化动画类型,我们可以制做出丰富的界面效果。主要有基于时间的动画和基于属性的动画。 1、Animatable 一个提供动画支持的抽象类。 继承 Object DispatcherObject Depende…...
跑腿代购app系统源码开发及功能分析
随着互联网技术的飞速发展和人们生活节奏的加快,跑腿代购服务作为一种便捷的生活方式,正逐渐渗透到我们日常生活的方方面面。从日常购物、餐饮外卖到文件传递、药品代购,跑腿服务以其高效、灵活的特点赢得了广大用户的青睐。而支撑这一服务高…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
智能职业发展系统:AI驱动的职业规划平台技术解析
智能职业发展系统:AI驱动的职业规划平台技术解析 引言:数字时代的职业革命 在当今瞬息万变的就业市场中,传统的职业规划方法已无法满足个人和企业的需求。据统计,全球每年有超过2亿人面临职业转型困境,而企业也因此遭…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...
Vue 实例的数据对象详解
Vue 实例的数据对象详解 在 Vue 中,数据对象是响应式系统的核心,也是组件状态的载体。理解数据对象的原理和使用方式是成为 Vue 专家的关键一步。我将从多个维度深入剖析 Vue 实例的数据对象。 一、数据对象的定义方式 1. Options API 中的定义 在 Options API 中,使用 …...
使用ch340继电器完成随机断电测试
前言 如图所示是市面上常见的OTA压测继电器,通过ch340串口模块完成对继电器的分路控制,这里我编写了一个脚本方便对4路继电器的控制,可以设置开启时间,关闭时间,复位等功能 软件界面 在设备管理器查看串口号后&…...
【threejs】每天一个小案例讲解:创建基本的3D场景
代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone,无需安装依赖,直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景(Scene) 使用 THREE.Scene(…...
