蓝桥杯刷题记录之蓝桥王国

2024-03-31 19:44
文章标签 记录 蓝桥 王国 杯刷题

本文主要是介绍蓝桥杯刷题记录之蓝桥王国,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

只是记录

这题用迪杰斯特拉来就行,我写的是堆优化版本


import java.util.*;public class Main{static Scanner s = new Scanner(System.in);static int n,m,startPoint=1;static List<Edge>[] table;//邻接表,因为是稀疏图static long[] dist;static boolean[] used;public static void main(String[] args) {n = s.nextInt();m = s.nextInt();used = new boolean[n+1];dist = new long[n+1];table = new List[n+1];for(int i=0;i<=n;i++)table[i] = new ArrayList<>();for(int i=0;i<m;i++){int start = s.nextInt();int end = s.nextInt();long distance = s.nextLong();table[start].add(new Edge(end,distance));}dijkstra();for(int i=1;i<=n;i++){System.out.print(dist[i]==Long.MAX_VALUE?"-1 ":dist[i]+" ");}s.close();}static void dijkstra(){Arrays.fill(dist,Long.MAX_VALUE);dist[startPoint]=0;PriorityQueue<Edge> pq = new PriorityQueue<>((x,y)->x.distance.compareTo(y.distance));pq.add(new Edge(startPoint,0));while (!pq.isEmpty()){Edge poll = pq.poll();int t = poll.end;if(used[t])continue;used[t] = true;for(Edge item: table[t]){int vertex  = item.end;long distance = item.distance;if(!used[vertex] && dist[vertex] > dist[t]+distance){dist[vertex] = dist[t]+distance;pq.add(new Edge(vertex,dist[vertex]));}}}}
}
class Edge{int end;// 终点Long distance;//距离public Edge(int end,long distance){this.end = end;this.distance = distance;}
}

这篇关于蓝桥杯刷题记录之蓝桥王国的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/865176

相关文章

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在,但一直侥幸自己应该不会用到它,所以一直没有开始学习。然而人生这么长,怎就确定自己不会用到呢? 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真,手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码,方便自己以后使用和修正。 2 思路整理 作为一个IC d

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

SSM项目使用AOP技术进行日志记录

本步骤只记录完成切面所需的必要代码 本人开发中遇到的问题: 切面一直切不进去,最后发现需要在springMVC的核心配置文件中中开启注解驱动才可以,只在spring的核心配置文件中开启是不会在web项目中生效的。 之后按照下面的代码进行配置,然后前端在访问controller层中的路径时即可观察到日志已经被正常记录到数据库,代码中有部分注释,看不懂的可以参照注释。接下来进入正题 1、导入m

flume系列之:记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之:记录一次flume agent进程被异常oom kill -9的原因定位 一、背景二、定位问题三、解决方法 一、背景 flume系列之:定位flume没有关闭某个时间点生成的tmp文件的原因,并制定解决方案在博主上面这篇文章的基础上,在机器内存、cpu资源、flume agent资源都足够的情况下,flume agent又出现了tmp文件无法关闭的情况 二、

Linux常用工具与命令日常记录(长期更新)

Linux常用工具与命令日常记录(长期更新) 目录 1.本地复制到远程2.Linux压缩拆包与解压3.生成随机密码4.ubuntu默认Python版本设置5.计算当前文件夹中文件数量6.windows中编写shell脚本,在Linux运行出错7.history 历史命令显示时间用户8.Ubuntu18.04设置源、网卡9.Ubuntu18.04设置网卡10.Ubuntu:自定义开

Excel和Word日常使用记录:

Excel使用总结 表格颜色填充: 合并单元格: 选中你要合并的单元格区域。按下快捷键 Alt + H,然后松开这些键。再按下 M,接着按 C。这个组合键执行的操作是:Alt + H:打开“主页”选项卡。M:选择“合并单元格”选项。C:执行“合并并居中”操作。 插入行: 在Excel中,插入一行的快捷键是:Windows:选择整行(可以点击行号)。按下 Ctrl + Sh

野火霸天虎V2学习记录

文章目录 嵌入式开发常识汇总1、嵌入式Linux和stm32之间的区别和联系2、stm32程序下载方式3、Keil5安装芯片包4、芯片封装种类5、STM32命名6、数据手册和参考手册7、什么是寄存器、寄存器映射和内存映射8、芯片引脚顺序9、stm32芯片里有什么10、存储器空间的划分11、如何理解寄存器说明12、如何操作寄存器的某一位 STM32F407芯片学习1、stm32单片机启动流程s