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

【备战蓝桥杯系列】单源最短路径Dijkstra算法模板

Dijkstra算法模板

蓝桥杯中也是会考到图论最短路的,一旦考到,基本是不会太难的,只要知道板子就基本能拿分了。

两个板子如下

朴素Dijkstra算法

适应情况:稠密图,正权边

时间复杂度 O(n^2 + m)

int dijkst(){memset(dist, 0x3f, sizeof dist);//初始化成无穷大dist[1] = 0;for(int i = 1; i <= n; i ++ ){//寻找所有点到起点的最短距离int t = -1;for(int j = 1; j <= n; j ++ ){//找到未确定且距离最小的点if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}st[t] = true;//将该点确定for(int j = 1; j <= n; j ++ ){//用该点距离更新其他点dist[j] = min(dist[j], dist[t] + g[t][j]);}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
堆优化版dijkstra

适应情况:稀疏图,正权边

时间复杂度 O(mlongn) — 堆每次更新值时间复杂度是logn,而通过邻接表来存,

​ 每次只遍历与该点相连的边,所以总的遍历次数是m,故时间复杂度是mlogn

int dijkstra(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>,greater<PII>> heap;heap.push({0, 1});while(heap.size()){//第一步遍历auto t = heap.top();//第二步①找出未确定的距离最小的点heap.pop();int dis = t.first, ver = t.second;if(st[ver]) continue;st[ver] = true;//第二步②将该最短距离确定下来for(int i = he[ver]; i != -1; i = ne[i]){//第三步 更新dist数组int j = e[i];if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];heap.push({dist[j], j});//此处会产生冗余,对于产生新的最短距离的点,其{旧值距离,点}会成为冗余数据,//下沉到堆得下半部分}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

相关文章:

【备战蓝桥杯系列】单源最短路径Dijkstra算法模板

Dijkstra算法模板 蓝桥杯中也是会考到图论最短路的&#xff0c;一旦考到&#xff0c;基本是不会太难的&#xff0c;只要知道板子就基本能拿分了。 两个板子如下 朴素Dijkstra算法 适应情况&#xff1a;稠密图&#xff0c;正权边 时间复杂度 O(n^2 m) int dijkst(){memse…...

嵌入式系统中端口号的理解与分析

每当看到有人的简历上写着熟悉 tcp/ip, http 等协议时, 我就忍不住问问他们: 你给我说说, 端口是啥吧! 可惜, 很少有人能说得让人满意... 所以这次就来谈谈端口(port), 这个熟悉的陌生人. 在此过程中, 还会谈谈间接层, naming service 等概念, IoC, 依赖倒置等原则以及 TCP 协议…...

3.自定义工程目录配置CMakeLists

问题背景 熟悉stm32keil开发的都知道&#xff0c;我们在编写不同的外设时&#xff0c;通常都会单独编写一个app文件夹或者是user文件夹之类的来存放不同外设功能的源文件和头文件。 在前面一节2.构建第一个工程并烧录到ESP32开发板-CSDN博客中&#xff0c;我们是使用了一个乐鑫…...

Vue3.0里为什么要用 Proxy API 替代 defineProperty API

一、Object.defineProperty 定义&#xff1a;Object.defineProperty() 方法会直接在一个对象上定义一个新属性&#xff0c;或者修改一个对象的现有属性&#xff0c;并返回此对象 为什么能实现响应式 通过defineProperty 两个属性&#xff0c;get及set get 属性的 getter 函…...

c++初阶------类和对象(下)

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…...

PMP考试:如何高效学习PMBOK?

PMBOK&#xff08;项目管理知识体系指南&#xff09;是PMP考试的核心教材&#xff0c;学习PMBOK对于备考PMP考试至关重要。那么我将分享一些高效学习PMBOK的方法和技巧&#xff0c;帮助同学们更好地掌握项目管理知识。 一、制定学习计划 在学习PMBOK之前&#xff0c;制定一个详…...

个人博客网站前端页面的实现

博客网站前端页面的实现 博客登录页 相关代码 login.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…...

Kotlin Retrofit 网络请求

一、添加依赖&#xff1a; //Retrofit 网络请求implementation("com.squareup.retrofit2:retrofit:2.3.0")implementation("com.squareup.retrofit2:converter-gson:2.3.0")//json转换 二、创建单例类&#xff1a; package com.example.buju.httpimport …...

pyside6 pytq PyDracula QVideoWidget视频只有声音没有画面

解决方案&#xff1a; 先不使用框架&#xff0c;纯pyside6代码&#xff0c;如果添加视频有画面有声音&#xff0c;那可以排除是硬件问题&#xff0c;如果没有画面只有声音&#xff0c;可能是视频解码器无法解码&#xff0c;换个格式的视频文件如果只有使用PyDracula 出问题&am…...

Python爬网页,不确定网页的编码,不需要用第三方库

Python爬网页&#xff0c;不确定网页的编码&#xff0c;不需要用第三方库&#xff0c;自己写个判断&#xff0c;乱拳打死老师傅 detect试了&#xff0c;不好用 apparent_encoding试了&#xff0c;不好用 encoding试了&#xff0c;不好用 headers里get试了&#xff0c;不好用…...

Web测试的基础流程(外加测试过程需要的注意5点)

前言 在Web工程过程中&#xff0c;基于Web系统的测试、确认和验收是一项重要而富有挑战性的工作。基于Web的系统测试与传统的软件测试不同&#xff0c;它不但需要检查和验证是否按照设计的要求运行&#xff0c;而且还要测试系统在不同用户的浏览器端的显示是否合适。 重要的是…...

项目解决方案:视频监控接入和录像系统设计方案(下)

目 录 1.概述 2. 建设目标及需求 2.1建设总目标 2.2 需求描述 ​2.3 需求分析 3.设计依据与设计原则 3.1设计依据 3.2 设计原则 4.建设方案设计 4.1系统方案设计 4.2组网说明 5.产品介绍 5.1视频监控综合资源管理平台介绍 5.2视频录像服务器和存储 5.2.…...

Python爬虫-使用Prefect框架实现一个可视化爬虫项目

前言 本文是该专栏的第19篇,后面会持续分享python爬虫干货知识,记得关注。 相信有的同学,在处理爬虫项目的时候,有时也会需要你将爬虫项目进行一个可视化展示,方便管理者能及时详细的了解当前爬虫任务的执行进度以及执行情况,甚至需要做一个爬虫监控预警的可视化任务。 …...

[hive面试真题]-基础理论篇

hive的工作流程 hive中分区表,分桶表 工作中hive分区表的应用示例 发现hive分区中的数据不对怎么处理 hive出现code 1 2 3 什么原因 ,怎么处理 工作中hive常见的文件格式 .压缩格式 工作时常用的hive函数 谈谈对窗口函数的理解 hive中如果出现数据倾斜 ,怎么发现 ,怎么…...

【其他】sd卡的照片在相机上能看到在电脑上却看不到

sd卡的照片在相机上能看到在电脑上却看不到 前情提要&#xff1a;太长不看版解决办法&#xff1a;思路&#xff1a;一、首先考虑恢复数据二、 解决文件后缀是exe的问题 前情提要&#xff1a; 在相机里可以看到照片和视频&#xff0c;但是SD卡通过读卡器插入电脑看不到&#x…...

Linux 之六:系统性能监控和挂载

系统性能 Linux系统中&#xff0c;有许多命令用于监测和分析性能指标。以下是一些常用的Linux性能分析命令&#xff1a; top&#xff1a;实时查看并监控CPU、内存以及各个进程的资源占用情况。htop&#xff08;需要安装&#xff09;&#xff1a;一个增强版的 top 命令&#x…...

【Web】浅聊Java反序列化之C3P0——JNDI注入利用

目录 简介 原理分析 EXP 前文&#xff1a;【Web】浅聊Java反序列化之C3P0——URLClassLoader利用 【Web】浅聊Java反序列化之C3P0——不出网Hex字节码加载利用 简介 出网的情况下&#xff0c;这个C3P0的Gadget可以和fastjson&#xff0c;Snake YAML , JYAML,Yamlbeans , …...

Java项目:基于Springboot+vue实现的付费自习室系统设计与实现(源码+数据库+毕业论文)附含微信小程序端代码

一、项目简介 本项目是一套基于Springbootvue实现的付费自习室系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、…...

C++写食堂菜品管理系统

说明:本博文来自CSDN-问答板块,题主提问。 需要:学校拟开发一套食堂菜品管理系统,以便对菜品和同学们的评价进行管理,其中包含如下信息: 商户:商户名称、柜面位置、电话…… 菜品:菜品编号、菜品名称、价格、所属商户…… 学生:注册账号、昵称、电话…… 食堂里的商户…...

vue 在线预览word

1 mammoth 先找的是mammoth这个插件yarn add mammoth,版本是1,7.0 参考网上的示例使用如下&#xff1a; import mammoth from "mammoth"; const vHtml ref("") const readExcelFromRemoteFile (url) >{var xhr new XMLHttpRequest();xhr.open("…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...