【代码随想录Day58】图论Part09
dijkstra(堆优化版)精讲
题目链接/文章讲解:代码随想录
import java.util.*;class Edge {int to; // 邻接顶点int val; // 边的权重Edge(int to, int val) {this.to = to;this.val = val;}
}class Pair<U, V> {public final U first; // 节点public final V second; // 从源点到该节点的权重public Pair(U first, V second) {this.first = first;this.second = second;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取节点数和边数int n = scanner.nextInt();int m = scanner.nextInt();// 创建图的邻接表List<List<Edge>> graph = new ArrayList<>(n + 1);for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}// 读取边的信息for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();graph.get(p1).add(new Edge(p2, val));}int start = 1; // 起点int end = n; // 终点// 存储从源点到每个节点的最短距离int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0; // 起始点到自身的距离为0// 记录顶点是否被访问过boolean[] visited = new boolean[n + 1];// 优先队列,用于选择当前最短路径的节点PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(pair -> pair.second));// 初始化队列,添加源点pq.add(new Pair<>(start, 0));while (!pq.isEmpty()) {// 取出当前距离源点最近的节点Pair<Integer, Integer> cur = pq.poll();int currentNode = cur.first;// 如果该节点已被访问,跳过if (visited[currentNode]) continue;// 标记该节点为已访问visited[currentNode] = true;// 更新与当前节点相连的邻接节点的路径for (Edge edge : graph.get(currentNode)) {// 如果该邻接节点未被访问且新路径更短,则更新最短路径if (!visited[edge.to] && minDist[currentNode] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[currentNode] + edge.val;pq.add(new Pair<>(edge.to, minDist[edge.to])); // 将新路径加入优先队列}}}// 输出结果System.out.println(minDist[end] == Integer.MAX_VALUE ? -1 : minDist[end]);}
}
Bellman_ford 算法精讲
题目链接/文章讲解:代码随想录
import java.util.*;public class Main {// 定义边的内部类static class Edge {int from; // 起始节点int to; // 结束节点int val; // 边的权重public Edge(int from, int to, int val) {this.from = from;this.to = to;this.val = val;}}public static void main(String[] args) {// 输入处理Scanner scanner = new Scanner(System.in);int numberOfNodes = scanner.nextInt(); // 节点数量int numberOfEdges = scanner.nextInt(); // 边的数量List<Edge> edges = new ArrayList<>();// 读取每一条边的信息for (int i = 0; i < numberOfEdges; i++) {int from = scanner.nextInt();int to = scanner.nextInt();int val = scanner.nextInt();edges.add(new Edge(from, to, val));}// 存储从起点到各节点的最小距离int[] minDistance = new int[numberOfNodes + 1];Arrays.fill(minDistance, Integer.MAX_VALUE); // 初始化最小距离为无穷大minDistance[1] = 0; // 起点到自身的距离为0// 执行 Bellman-Ford 算法,放松所有边 n-1 次for (int i = 1; i < numberOfNodes; i++) {for (Edge edge : edges) {// 如果起始节点的距离不为无穷大,且通过当前边可以找到更短的路径if (minDistance[edge.from] != Integer.MAX_VALUE) {int newDistance = minDistance[edge.from] + edge.val;if (newDistance < minDistance[edge.to]) {minDistance[edge.to] = newDistance; // 更新最小距离}}}}// 输出结果if (minDistance[numberOfNodes] == Integer.MAX_VALUE) {System.out.println("unconnected"); // 如果目标节点不可达} else {System.out.println(minDistance[numberOfNodes]); // 输出目标节点的最小距离}scanner.close(); // 关闭扫描器以释放资源}
}
相关文章:
【代码随想录Day58】图论Part09
dijkstra(堆优化版)精讲 题目链接/文章讲解:代码随想录 import java.util.*;class Edge {int to; // 邻接顶点int val; // 边的权重Edge(int to, int val) {this.to to;this.val val;} }class Pair<U, V> {public final U first; …...
_或者%关键字模糊匹配查出所有数据
1、问题 sql模糊匹配,如果页面输入_或者%,可以查出所有数据。 (1) SELECT * FROM test WHERE sfsc N and zdzwm like %%% (2) SELECT * FROM test WHERE sfsc N and zdzwm like %_% 2、解决方案 (1)mysql数据库 加转义字…...
【Python】转换得到图片的rgb565格式数据
使用方法:首先在代码同级目录创建input_images文件夹,然后将需要转换的图片放进去。 然后根据你的需要,修改代码最下面的crop_size、resize以及file_name。 最后点击运行,即可得到图片的rgb565格式数据 from PIL import Image, I…...
隨筆 20241024 Kafka中的ISR列表:分区副本的族谱
在分布式系统中,数据的一致性和可靠性至关重要。Apache Kafka作为一个强大的流处理平台,利用其分区和副本机制来确保这些特性。在Kafka中,ISR(In-Sync Replicas)列表是一个关键概念,它用来追踪与领导者副本…...

【python】爬虫
下载与批量下载 import requests #第三方库,没有下载的下载一下 pip install requests#爬虫下载图片 resrequests.get("url") print(res.content)#二进制字节流#写文件 with open("beauty.jpg","wb")as f:f.write(res.content)#批量…...

大语言模型数据类型与环境安装(llama3模型)
文章目录 前言一、代码获取一、环境安装二、大语言模型数据类型1、基本文本指令数据类型2、数学指令数据类型3、几何图形指令数据类型4、多模态指令数据类型5、翻译指令数据类型三、vscode配置四、相关知识内容1、理解softmax内容2、torch相关函数nn.Embedding函数torch.nn.fun…...
JS:列表操作
目录 1、列表截取2、列表数据包含3、列表筛选4、极值操作5、获取列表对象某一属性构建列表6、获取元素在列表中的下标7、列表去重 1、列表截取 列表截取:List.slice(start, end),左闭右开 var dataList [1,2,3,4,5,6] var resultList dataList.slice(0…...

ECharts 折线图 / 柱状图 ,通用配置标注示例
option {tooltip: { // 关于提示框(tooltip)的配置// 显示某一个去掉trigger: axis,显示一起显示 trigger: axistrigger: axis},legend: {top: bottom, // 显示标注位置// textStyle: {// color: "#000", // 设置图例文字颜…...
统计数据集的TXT、XML及JSON标注文件中各类别/每个标签的数量
在计算机视觉和深度学习领域,标注文件是模型训练的重要组成部分。无论是图像分类、目标检测还是图像分割,正确的标注能够显著提升模型的性能。在实际应用中,我们需要快速了解每个类别的样本数量,以便进行数据分析、平衡类别分布或…...
Facebook登录客户追踪:了解用户访问路径,优化客户体验
随着数字化转型的不断加速,精准的客户数据收集和用户行为追踪成为企业提升用户体验和优化业务流程的关键。Facebook登录作为一种便捷的第三方登录方式,已经被广泛应用于各类网站和应用中。它不仅简化了用户的注册与登录流程,还帮助企业获得用…...

NUUO摄像头 debugging_center_utils 远程命令执行漏洞复现
0x01 产品描述: NUUO摄像头是由中国台湾NUUO公司生产的一款网络视频录像机(Network Video Recorder,简称NVR),广泛应用于零售、交通、教育、政府和银行等多个领域。它能够同时管理多个IP摄像头,…...
Nginx 的讲解和案例示范
一、基础理解 1.1 Nginx 是什么? Nginx是一个高性能的 Web 服务器和反向代理服务器,同时也可以作为邮件代理服务器。Nginx 以其高并发处理能力、低内存消耗和丰富的功能受到广泛欢迎。 主要功能: 静态资源服务:高效地提供 HTM…...
微信小程序元素水平居中或垂直居中
最近在做一个微信小程序的项目,其中涉及到css样式实现将<navigator>标签内的图片和文本元素垂直排列,并水平居中。在尝试实现的过程中,将元素在标签内的所有排列情况都顺带实现了。上代码: index.wxml <navigator url&…...

ClickHouse 神助攻:纽约城市公共交通管理(MTA)数据应用挑战赛
本文字数:13198;估计阅读时间:33 分钟 作者:The PME Team 本文在公众号【ClickHouseInc】首发 我们一向对开放数据挑战充满热情,所以当发现 MTA(城市交通管理局)在其官网发起了这样的挑战时&…...

ELK + Filebeat + Spring Boot:日志分析入门与实践(二)
目录 一、环境 1.1 ELKF环境 1.2 版本 1.3 流程 二、Filebeat安装 2.1 安装 2.2 新增配置采集日志 三、logstash 配置 3.1 配置输出日志到es 3.2 Grok 日志格式解析 3.2 启动 logstash 3.3 启动项目查看索引 一、环境 1.1 ELKF环境 springboot项目:w…...

使用 Docker Compose 将数据版 LobeChat 服务端部署
LobeChat 是一个基于 TypeScript 的开源聊天机器人项目,支持本地部署和接入多个大语言模型。本文介绍如何使用 Docker Compose 将 LobeChat 服务端及其数据库部署到生产环境,让您拥有一个私有化的、可定制的 AI 聊天助手。 一、部署前准备 服务器&…...
python如何完成金融领域的数据分析,思路以及常见的做法是什么?
引言 在现代金融领域,数据分析已成为决策支持的重要工具。随着金融市场的复杂性和数据量的激增,传统的分析方法已无法满足需求。 Python作为一种强大的编程语言,凭借其丰富的库和工具,成为金融数据分析的首选语言之一。 本文将探讨如何利用Python进行金融数据分析,包括…...

密码管理工具实现
该文档详细描述了实现一个简单的密码管理工具的过程,工具基于PHP和MySQL构建,支持用户注册、密码存储、管理以及角色权限控制等核心功能。 系统架构设计 技术栈:PHP(后端逻辑)、MySQL(数据存储)…...
构造函数和new操作符 - 2024最新版前端秋招面试短期突击面试题【100道】
构造函数和new操作符 - 2024最新版前端秋招面试短期突击面试题【100道】 🏗️ 在JavaScript中,构造函数和new操作符是创建对象的重要方式。深入理解它们的基本概念和用法,可以帮助你更有效地使用JavaScript进行开发。以下是关于构造函数和ne…...

6.Linux按键驱动-阻塞与非阻塞
默认打开文件时候是阻塞的 当设置打开方式为非阻塞时,无数据时会返回。 当设置打开方式为阻塞时,无数据的时候会等待1.设置打开方式为非阻塞 立即返回,无法读出,返回-1 2.设置为阻塞 核心在于驱动程序中的.read函数的支持 …...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...