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

代码随想录Day76(图论Part11)

97.小明逛公园(Floyd)

题目:97. 小明逛公园 (kamacoder.com)

思路:

答案
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 顶点数int m = scanner.nextInt();  // 边数int[][] grid = new int[n + 1][n + 1];final int INF = 10005; // 因为边的最大距离是10^4// 初始化图的邻接矩阵for (int i = 1; i <= n; i++) {Arrays.fill(grid[i], INF);grid[i][i] = 0; // 自己到自己的距离为0}// 读取边的信息并填充邻接矩阵for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();grid[p1][p2] = val;grid[p2][p1] = val; // 注意这里是双向图}// 开始 Floyd-Warshall 算法for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);}}}// 读取查询并输出结果int z = scanner.nextInt(); // 查询次数while (z-- > 0) {int start = scanner.nextInt();int end = scanner.nextInt();if (grid[start][end] == INF) {System.out.println(-1);} else {System.out.println(grid[start][end]);}}scanner.close();}
}
小结

126.骑士的攻击(A*算法)

题目:126. 骑士的攻击 (kamacoder.com)

思路:毫无疑问是最难的一题

答案
import java.util.*;class Knight implements Comparable<Knight> {int x, y, g, h, f;public Knight(int x, int y, int g, int h) {this.x = x;this.y = y;this.g = g;this.h = h;this.f = g + h;}@Overridepublic int compareTo(Knight k) {return Integer.compare(this.f, k.f); // 从小到大排序}
}public class Main {static int[][] moves = new int[1001][1001];static int[][] dir = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},{2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int b1, b2;static PriorityQueue<Knight> que = new PriorityQueue<>();public static int heuristic(Knight k) {return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号,这样可以提高精度}public static void astar(Knight start) {que.add(start);while (!que.isEmpty()) {Knight cur = que.poll();if (cur.x == b1 && cur.y == b2)break;for (int i = 0; i < 8; i++) {int nextX = cur.x + dir[i][0];int nextY = cur.y + dir[i][1];if (nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000)continue;if (moves[nextX][nextY] == 0) {moves[nextX][nextY] = moves[cur.x][cur.y] + 1;int nextG = cur.g + 5; // 马走日,1 * 1 + 2 * 2 = 5int nextH = heuristic(new Knight(nextX, nextY, 0, 0));que.add(new Knight(nextX, nextY, nextG, nextH));}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- > 0) {int a1 = scanner.nextInt();int a2 = scanner.nextInt();b1 = scanner.nextInt();b2 = scanner.nextInt();for (int[] row : moves) Arrays.fill(row, 0);Knight start = new Knight(a1, a2, 0, heuristic(new Knight(a1, a2, 0, 0)));astar(start);que.clear(); // 清空队列System.out.println(moves[b1][b2]);}scanner.close();}
}

相关文章:

代码随想录Day76(图论Part11)

97.小明逛公园&#xff08;Floyd&#xff09; 题目&#xff1a;97. 小明逛公园 (kamacoder.com) 思路&#xff1a; 答案 import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();…...

工程化:Commitlint / 规范化Git提交消息格式

一、理解Commitlint Commitlint是一个用于规范化Git提交消息格式的工具。它基于Node.js&#xff0c;通过一系列的规则来检查Git提交信息的格式&#xff0c;确保它们遵循预定义的标准。 1.1、Commitlint的核心功能 代码规则检查&#xff1a;Commitlint基于代码规则进行检查&a…...

电脑有线网卡和无线网卡的MAC地址

电脑上的无线网卡和有线网卡是两种不同类型的网络接口卡&#xff0c;它们各自有不同的功能和连接方式。 无线网卡&#xff1a; 功能&#xff1a;无线网卡允许计算机通过无线信号连接到网络&#xff0c;通常是Wi-Fi网络。连接方式&#xff1a;无需物理电缆&#xff0c;通过无线…...

代码随想录-DAY②-数组——leetcode 977 | 209

977 思路 使用两个指针分别指向位置 0 和 n−1&#xff0c;每次比较两个指针对应的数&#xff0c;选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。 时间复杂度&#xff1a;O(n) 空间复杂度&#xff1a;O(1) 代码 class Solution { pub…...

稀疏数组搜索

题目链接 稀疏数组搜索 题目描述 注意点 字符串数组中散布着一些空字符串words的长度在[1, 1000000]之间字符串数组是排好序的数组中的字符串不重复 解答思路 因为数组中的字符串是排好序的&#xff0c;所以首先想到的是二分查找&#xff0c;先将数组中长度与s相同的字符串…...

存储器类型介绍

存储器 ROM 我们一般把手机和电脑的硬盘当作ROM。ROM的全称是&#xff1a;Read Only Memery&#xff0c;只读存储器&#xff0c;就是只能读不能写的存储器。但是现在的ROM不仅可以读&#xff0c;还可以写数据&#xff0c;比如给手机下载APP&#xff0c;就是给手机上的ROM写数据…...

论文学习笔记1:Federated Graph Neural Networks: Overview, Techniques, and Challenges

文章目录 一、introduction二、FedGNN术语与分类2.1主要分类法2.2辅助分类法 三、GNN-ASSISTED FL3.1Centralized FedGNNs3.2Decentralized FedGNNs 四、FL-ASSISTED GNNS4.1horizontal FedGNNs4.1.1Clients Without Missing Edges4.1.1.1Non-i.i.d. problem4.1.1.2Graph embed…...

[数据集][目标检测]轮椅检测数据集VOC+YOLO格式13826张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;13826 标注数量(xml文件个数)&#xff1a;13826 标注数量(txt文件个数)&#xff1a;13826 标…...

视频剪辑音乐自动卡点Pr插件 BeatEdit v2.2 免费下载

Premiere Pro 视频剪辑音乐自动卡点鼓点节拍插件 BeatEdit v2.2.000 下载地址 https://prmuban.com/39091.html BeatEdit 检测音乐中的节拍并在 Premiere Pro 时间轴中为它们生成标记。 创建与音乐同步的自动编辑&#xff0c;或让 BeatEdit 协助您的手动编辑过程。 2.2.000&am…...

【INTEL(ALTERA)】为什么Nios® II构建流程报告无法在 Windows WSL 上确定程序大小?

目录 说明 解决方法 说明 由于英特尔 Quartus Prime 专业版软件 19.3 版中的 nios2-elf-stackreport 实用程序出现问题&#xff0c;nios2-elf-stackreport 实用程序确实如此 不报告程序大小或堆栈堆栈大小。 解决方法 要解决此问题&#xff0c;编辑 nios2-stackreport.pl …...

2024年第十四届APMCM亚太地区大学生数学建模竞赛

C 题 基于量子计算的物流配送问题 随着电子商务的迅猛发展&#xff0c;电商平台对物流配送的需求日益增长。为了确保货物能够按时、高效地送达消费者手中&#xff0c;电商平台与第三方物流公司建立了紧密的合作关系。然而&#xff0c;面对大量的货物和多样的目的地&#xff0c…...

删除账户相关信息

功能需求 获取正确的待删除账户名杀死系统中正在运行的属于该账户的进程确认系统中属于该账户的所有文件删除该账户 1. 获取正确的待删除账户名 #让用户输入账户名 read -t 10 -p "please input account name: " accountif [ -z $account ] thenecho "account…...

JavaSE (Java基础):面向对象(下)

8.7 多态 什么是多态&#xff1f; 即同一方法可以根据发送对象的不同而采用多种不同的方式。 一个对象的实际类型是确定的&#xff0c;但可以指向对象的引用的类型有很多。在句话我是这样理解的&#xff1a; 在实例中使用方法都是根据他最开始将类实例化最左边的类型来定的&…...

Element中的日期时间选择器DateTimePicker和级联选择器Cascader

简述&#xff1a;在Element UI框架中&#xff0c;Cascader&#xff08;级联选择器&#xff09;和DateTimePicker&#xff08;日期时间选择器&#xff09;是两个非常实用且常用的组件&#xff0c;它们分别用于日期选择和多层级选择&#xff0c;提供了丰富的交互体验和便捷的数据…...

Construct公司 从 0 到 1 基于 Kitex+Istio 的微服务系统建设

本文根据 2024 年 5 月 25 日在上海举办的“云原生✖️AI 时代的微服务架构与技术实践”CloudWeGo 技术沙龙上海站活动中&#xff0c;Construct 服务端总监 Jason 的演讲《从 0 到 1 基于 Kitex Istio 的微服务系统建设》整理而来。 在微服务架构的浪潮中&#xff0c;企业面临…...

day04-组织架构

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1.组织架构-树组件应用树形组件-用层级结构展示信息&#xff0c;可展开或折叠。 2.组织架构-树组件自定义结构3.组织架构-获取组织架构数据4.组织架构-递归转化树形…...

Web3 开发者入门手册:技能、工具和职业前景

原文&#xff1a;https://remote3.co/blog-post/how-to-become-a-web3-developer 作者&#xff1a;Paul Anderson 编译&#xff1a;TinTinLand Web3 是 2024 年科技领域最受瞩目的话题之一——Web3 令人激动的实用潜力可以跨越多个行业&#xff0c;早期采用者更有机会在未来…...

元宇宙虚拟实景展馆树立客户对企业的信任和好感

在数字化浪潮的推动下&#xff0c;企业迎来了前所未有的营销新机遇——3D数字展厅。3D数字展厅作为现代营销中的新型工具&#xff0c;不仅是企业与客户互动、传递信息的桥梁&#xff0c;更是企业展示实力、彰显品牌魅力的舞台。 辽宁3D数字展厅制作以其独特的设计理念和先进的制…...

【C语言】宏定义在 a.c 中定义,如何在 b.c 中使用?

宏定义的概念和使用原理 在 C 语言中&#xff0c;宏定义是一种预处理器指令&#xff0c;用于定义常量或者宏函数。宏在编译之前由预处理器展开&#xff0c;因此可以用来提高代码的可读性和维护性。宏定义使用 #define 指令&#xff0c;形式如下&#xff1a; #define 宏名 替换…...

vue3 滚动条滑动到元素位置时,元素加载

水个文 效果 要实现的思路就是&#xff0c;使用IntersectionObserver 检测元素是否在视口中显示&#xff0c;然后在通过css来进行动画载入。 1.监控元素是否视口中显示 const observer new IntersectionObserver((entries) > {entries.forEach((entry) > {if (entry.i…...

基于ESP32的智能电池充电器设计:多化学体系支持与模块化架构

1. 项目概述&#xff1a;打造一台全能的“电池医生”手头攒了一堆不同化学体系的电池&#xff0c;从航模用的4S锂聚合物电池&#xff0c;到应急灯里的12V铅酸电池&#xff0c;再到各种工具里的镍氢、锂离子电池&#xff0c;每次充电都得翻出好几个不同的充电器&#xff0c;桌面…...

大佬推荐的网络安全学习路线(从基础到高级,超级详细)

大佬推荐的网络安全学习路线&#xff08;从基础到高级&#xff0c;超级详细&#xff09; 说起网络安全&#xff0c;你可能会担心它是一个过时的行业。有人说&#xff0c;网络安全快卷死了&#xff0c;你既要攻又要防&#xff0c;并且随着技术的发展&#xff0c;你还要不断地学…...

Ubuntu经常安装软件

1、垃圾清理工具stacer sudo apt updatesudo apt install stacer apt cleanapt autocleanapt autoremove 2、类似与everything的工具Fsearcch 1sudo add-apt-repository ppa:christian-boxdoerfer/fsearch-stable 2sudo apt update 3sudo apt install fsearch (注&#xf…...

总线式智能提示灯系统设计:从恒流驱动到模块化架构

1. 项目概述&#xff1a;从传统到智能的剧场提示灯系统革新在剧场、演播室或者大型活动现场的后台&#xff0c;如果你待过&#xff0c;一定对那套“红灯停&#xff0c;绿灯行”的提示灯系统不陌生。导演或舞台监督通过对讲机喊“Standby”&#xff08;准备&#xff09;&#xf…...

终极指南:用D2DX让《暗黑破坏神2》在现代电脑上焕发新生

终极指南&#xff1a;用D2DX让《暗黑破坏神2》在现代电脑上焕发新生 【免费下载链接】d2dx D2DX is a complete solution to make Diablo II run well on modern PCs, with high fps and better resolutions. 项目地址: https://gitcode.com/gh_mirrors/d2/d2dx 还在为经…...

告别KITTI!用TartanAir数据集在Unreal Engine仿真环境里“虐”你的VSLAM算法(附保姆级下载与使用指南)

用TartanAir数据集在Unreal Engine中打造VSLAM算法的"极限考场"当你的视觉SLAM算法在KITTI数据集上跑出98%的准确率时&#xff0c;是否意味着它已经准备好应对真实世界的复杂场景&#xff1f;现实往往会给乐观的开发者当头一棒——实验室里的"优等生"在遇到…...

从配置到运行时:Forge Admin 的动态 API 配置管理是怎么做的

问题&#xff1a;同一个接口&#xff0c;今天要加认证、明天要加加密、后天要限流&#xff0c;这些行为散落在拦截器、过滤器、注解里&#xff0c;改一次牵一发动全身&#xff0c;怎么集中管理和动态刷新&#xff1f; 1. 这个问题在企业后台里为什么常见 在企业后台开发中&am…...

初创公司如何通过Taotoken快速为产品原型注入多种AI能力

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 初创公司如何通过Taotoken快速为产品原型注入多种AI能力 对于初创公司而言&#xff0c;资源有限、时间紧迫是常态。产品原型的快速…...

如何用500KB工具完全替代AWCC:AlienFX Tools终极指南

如何用500KB工具完全替代AWCC&#xff1a;AlienFX Tools终极指南 【免费下载链接】alienfx-tools Alienware systems lights, fans, and power control tools and apps 项目地址: https://gitcode.com/gh_mirrors/al/alienfx-tools 你是否厌倦了Alienware Command Cente…...

ZYNQ PS-SPI驱动W25Q80 Flash避坑指南:从寄存器配置到逻辑分析仪抓包全流程

ZYNQ PS-SPI驱动W25Q80 Flash实战避坑手册&#xff1a;从寄存器配置到信号抓包全解析 当你在Vitis Standalone环境下调试ZYNQ的PS-SPI与W25Q80 Flash通信时&#xff0c;是否遇到过这些场景&#xff1a;SPI时钟信号看似正常但数据始终对不上、擦除操作耗时远超预期、FIFO缓冲区莫…...