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

【代码随想录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&#xff08;堆优化版&#xff09;精讲 题目链接/文章讲解&#xff1a;代码随想录 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模糊匹配&#xff0c;如果页面输入_或者%&#xff0c;可以查出所有数据。 (1) SELECT * FROM test WHERE sfsc N and zdzwm like %%% (2) SELECT * FROM test WHERE sfsc N and zdzwm like %_% 2、解决方案 &#xff08;1&#xff09;mysql数据库 加转义字…...

【Python】转换得到图片的rgb565格式数据

使用方法&#xff1a;首先在代码同级目录创建input_images文件夹&#xff0c;然后将需要转换的图片放进去。 然后根据你的需要&#xff0c;修改代码最下面的crop_size、resize以及file_name。 最后点击运行&#xff0c;即可得到图片的rgb565格式数据 from PIL import Image, I…...

隨筆 20241024 Kafka中的ISR列表:分区副本的族谱

在分布式系统中&#xff0c;数据的一致性和可靠性至关重要。Apache Kafka作为一个强大的流处理平台&#xff0c;利用其分区和副本机制来确保这些特性。在Kafka中&#xff0c;ISR&#xff08;In-Sync Replicas&#xff09;列表是一个关键概念&#xff0c;它用来追踪与领导者副本…...

【python】爬虫

下载与批量下载 import requests #第三方库&#xff0c;没有下载的下载一下 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、列表截取 列表截取&#xff1a;List.slice(start, end)&#xff0c;左闭右开 var dataList [1,2,3,4,5,6] var resultList dataList.slice(0…...

ECharts 折线图 / 柱状图 ,通用配置标注示例

option {tooltip: { // 关于提示框&#xff08;tooltip&#xff09;的配置// 显示某一个去掉trigger: axis&#xff0c;显示一起显示 trigger: axistrigger: axis},legend: {top: bottom, // 显示标注位置// textStyle: {// color: "#000", // 设置图例文字颜…...

统计数据集的TXT、XML及JSON标注文件中各类别/每个标签的数量

在计算机视觉和深度学习领域&#xff0c;标注文件是模型训练的重要组成部分。无论是图像分类、目标检测还是图像分割&#xff0c;正确的标注能够显著提升模型的性能。在实际应用中&#xff0c;我们需要快速了解每个类别的样本数量&#xff0c;以便进行数据分析、平衡类别分布或…...

Facebook登录客户追踪:了解用户访问路径,优化客户体验

随着数字化转型的不断加速&#xff0c;精准的客户数据收集和用户行为追踪成为企业提升用户体验和优化业务流程的关键。Facebook登录作为一种便捷的第三方登录方式&#xff0c;已经被广泛应用于各类网站和应用中。它不仅简化了用户的注册与登录流程&#xff0c;还帮助企业获得用…...

NUUO摄像头 debugging_center_utils 远程命令执行漏洞复现

0x01 产品描述&#xff1a; ‌ NUUO摄像头‌是由中国台湾NUUO公司生产的一款网络视频录像机&#xff08;Network Video Recorder&#xff0c;简称NVR&#xff09;&#xff0c;广泛应用于零售、交通、教育、政府和银行等多个领域。它能够同时管理多个IP摄像头&#xff0c…...

Nginx 的讲解和案例示范

一、基础理解 1.1 Nginx 是什么&#xff1f; Nginx是一个高性能的 Web 服务器和反向代理服务器&#xff0c;同时也可以作为邮件代理服务器。Nginx 以其高并发处理能力、低内存消耗和丰富的功能受到广泛欢迎。 主要功能&#xff1a; 静态资源服务&#xff1a;高效地提供 HTM…...

微信小程序元素水平居中或垂直居中

最近在做一个微信小程序的项目&#xff0c;其中涉及到css样式实现将<navigator>标签内的图片和文本元素垂直排列&#xff0c;并水平居中。在尝试实现的过程中&#xff0c;将元素在标签内的所有排列情况都顺带实现了。上代码&#xff1a; index.wxml <navigator url&…...

ClickHouse 神助攻:纽约城市公共交通管理(MTA)数据应用挑战赛

本文字数&#xff1a;13198&#xff1b;估计阅读时间&#xff1a;33 分钟 作者&#xff1a;The PME Team 本文在公众号【ClickHouseInc】首发 我们一向对开放数据挑战充满热情&#xff0c;所以当发现 MTA&#xff08;城市交通管理局&#xff09;在其官网发起了这样的挑战时&…...

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项目&#xff1a;w…...

使用 Docker Compose 将数据版 LobeChat 服务端部署

LobeChat 是一个基于 TypeScript 的开源聊天机器人项目&#xff0c;支持本地部署和接入多个大语言模型。本文介绍如何使用 Docker Compose 将 LobeChat 服务端及其数据库部署到生产环境&#xff0c;让您拥有一个私有化的、可定制的 AI 聊天助手。 一、部署前准备 服务器&…...

python如何完成金融领域的数据分析,思路以及常见的做法是什么?

引言 在现代金融领域,数据分析已成为决策支持的重要工具。随着金融市场的复杂性和数据量的激增,传统的分析方法已无法满足需求。 Python作为一种强大的编程语言,凭借其丰富的库和工具,成为金融数据分析的首选语言之一。 本文将探讨如何利用Python进行金融数据分析,包括…...

密码管理工具实现

该文档详细描述了实现一个简单的密码管理工具的过程&#xff0c;工具基于PHP和MySQL构建&#xff0c;支持用户注册、密码存储、管理以及角色权限控制等核心功能。 系统架构设计 技术栈&#xff1a;PHP&#xff08;后端逻辑&#xff09;、MySQL&#xff08;数据存储&#xff09…...

构造函数和new操作符 - 2024最新版前端秋招面试短期突击面试题【100道】

构造函数和new操作符 - 2024最新版前端秋招面试短期突击面试题【100道】 &#x1f3d7;️ 在JavaScript中&#xff0c;构造函数和new操作符是创建对象的重要方式。深入理解它们的基本概念和用法&#xff0c;可以帮助你更有效地使用JavaScript进行开发。以下是关于构造函数和ne…...

6.Linux按键驱动-阻塞与非阻塞

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

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...