【最短路算法】SPFA
引入
在计算机科学的世界里,算法就像是星空中的繁星,各自闪烁着智慧的光芒。它们沉默而坚定,像是一群不语的哲人,默默地解答着世界的问题。
算法的步骤,如同优美的诗行,让复杂的问题在流转的字符中得以释放。它们如同山间清泉,从一座山峰流淌到另一座山峰,涤荡着问题的尘埃,揭示出真实的面貌。
它们像是一把把钥匙,打开了通往计算机科学的大门。我们用它们来解决问题,用它们来创造奇迹。它们是我们智慧的结晶,是我们对世界的理解和对未来的憧憬。
走进这个充满算法的世界,感受那智慧的光芒和诗意的韵律。让我们一起探索未知的领域,寻找那最美的风景和最珍贵的宝藏。
算法不仅是计算机科学的基础,更是我们生活的诗意所在。它们让我们看到了未来的希望,感受到了科技的魅力。所以,让我们一起拥抱算法,让它们为我们的生活增添色彩,为我们的世界带来更多的可能性。
算法就像是计算机科学中的一道道美食佳肴,它们各自拥有独特的味道和风味。有些算法如同细腻的法式甜点,复杂而精致,需要我们耐心地逐一品味;有些算法则如同朴实的乡村面包,简单而实用,让人感到亲切和温暖。
基本介绍
而在这茫茫的算法大海中,有一种算法闪烁着亮丽的光彩——最短路算法。
最短路算法是一种图论算法,用于在加权图中找到两个节点之间的最短路径。这种算法在现实生活中有着广泛的应用,例如:
- 交通规划:最短路算法可以用于城市交通规划,帮助确定最短路线,以减少交通拥堵和提高交通效率。
- 物流配送:在物流配送中,最短路算法可以帮助确定最短路径,以最小化运输成本和时间。
- 网络设计:在计算机网络中,最短路算法可以帮助确定最佳路由,以确保数据包能够以最快的速度传输。
- 地理信息系统:在地理信息系统中,最短路算法可以用于确定两点之间的最短路径,例如在地图上查找两点之间的最佳路线。
其中,SPFA是打开图论大门的一个钥匙,就让我们走进它吧。
思路
归根结底,SPFA就是宽搜,看看就懂了。
#include <bits/stdc++.h>
using namespace std;
struct edge{int x, y, c, pre;} a[410000];int alen, last[11100];
void ins(int x, int y, int c)//ins函数的功能是建立一条从x出发到y且长度为c的边
{a[++alen] = edge{x, y, c, last[x]}; 全局增加一条有向边,并赋值last[x] = alen; //建立边与边的联系(都是从x出发)
}int n, m, d[11100]; //d[i]表示目前i和出发点的最短距离
bool v[11100]; //v[i]等于true表示点i在更新队列中,等于false表示点i不在更新队列中
void spfa()
{memset(d, 63, sizeof(d));d[1] = 0; //初始化d数组,出发点为1,出发点到自己的距离为0memset(v, 0, sizeof(v)); v[1] = 1; //初始化v数组,v[1]等于1,表示出发点1进入队列deque<int> Q; Q.push_back(1); //定义更新队列,出发点进入更新队列while (!Q.empty()) //只要队列不为空,就表示还有点等着更新别的点{int x = Q.front(); //从队列中取出准备好更新别的点的点xfor (int k = last[x]; k; k = a[k].pre) //重点理解!k首相等于和x相连的最后一条边的编号。那么倒数第二条和x相连的边的编号是多少呢?在a[k].next可以找到{int y = a[k].y;if (d[y] > d[x] + a[k].c) //尝试用x的最短距离更新y的最短距离{d[y] = d[x] + a[k].c; //如果点被更新了,那么它马上有冲动(想进更新队列)要去更新它的"亲朋好友"(与之直接相连的点)if (v[y] == 0) //如果点y不在队列,则进入队列;如果已经在队列了,则不用再进入。{Q.push_back(y);v[y] = 1;}}}Q.pop_front(); //此时x已经更新完它的"亲朋好友",完成使命,退出队列Qv[x] = 0; //标记x已经不再队列,以后x有可能会再次进入队列}//队列没有点等着更新别的点了,那么意味着所有点的d值都是最优的if (d[n] == d[0]) printf("-1\n"); //d[0]为初始的最大值,d[n]等于d[0]表示点n没有被更新,即点n无法到达。else printf("%d", d[n]);
}
int main()
{scanf("%d%d", &n, &m);alen = 0;memset(last, 0, sizeof(last)); //注意构图之前一定要初始化,不然后果很严重!for (int i = 1; i <= m; i++){int x, y, c;scanf("%d%d%d", &x, &y, &c); //题目给出的是无向边,而我们的边目录是有向边ins(x, y, c);ins(y, x, c); //建立正向边、反向边}spfa();return 0;
}
详细注释都写在代码里面了,好好看。
例题
不放了,上洛谷自己查吧.
据说,一个欠揍的行为,需要一张图来安慰。
相关文章:
【最短路算法】SPFA
引入 在计算机科学的世界里,算法就像是星空中的繁星,各自闪烁着智慧的光芒。它们沉默而坚定,像是一群不语的哲人,默默地解答着世界的问题。 算法的步骤,如同优美的诗行,让复杂的问题在流转的字符中得以释…...

牛客网Verilog刷题——VL48
牛客网Verilog刷题——VL48 题目答案 题目 在data_en为高期间,data_in将保持不变,data_en为高至少保持3个B时钟周期。表明,当data_en为高时,可将数据进行同步。本题中data_in端数据变化频率很低,相邻两个数据间的变化&…...
Unity UGUI的Shadow(阴影)组件的介绍及使用
Unity UGUI的Shadow(阴影)组件的介绍及使用 1. 什么是Shadow(阴影)组件? Shadow(阴影)组件是Unity UGUI中的一个特效组件,用于在UI元素上添加阴影效果。通过调整阴影的颜色、偏移、模糊等属性,可以使UI元素看起来更加立体和有层次感。 2. …...

Kubernetes系列
文章目录 1 详解docker,踏入容器大门1.1 引言1.2 初始docker1.3 docker安装1.4 docker 卸载1.5 docker 核心概念和底层原理1.5.1 核心概念1.5.2 docker底层原理 1.6 细说docker镜像1.6.1 镜像的常用命令 1.7 docker 容器1.8 docker 容器数据卷1.8.1 直接命令添加1.8.2 Dockerfi…...

同步锁: synchronized
synchronized 1. synchronized的特性2. synchronized的使用3. synchronized的锁机制 1. synchronized的特性 原子性: 所谓原子性就是指一个操作或者多个操作,要么全部执行并且执行的过程不会被任何因素打断,要么就都不执行。可见性: 可见性是指多个线程…...
【微服务】springboot 多模块打包使用详解
目录 一、前言 1.1 为什么需要掌握多模块打包 二、工程模块概述 2.1 前后端不分离...

嵌入式工程师面试经常遇到的30个经典问题
很多同学说很害怕面试,看见面试官会露怯,怕自己的知识体系不完整,怕面试官考的问题回答不上了,所以今天为大家准备了嵌入式工程师面试经常遇到的30个经典问题,希望可以帮助大家提前准备,不再惧怕面试。 1&a…...

ER系列路由器多网段划分设置指南
ER系列路由器多网段划分设置指南 - TP-LINK 服务支持 TP-LINK ER系列路由器支持划分多网段,可以针对不同的LAN接口划分网段,即每一个或多个LAN接口对应一个网段;也可以通过一个LAN接口与支持划分802.1Q VLAN的交换机进行对接,实现…...
3 PostGIS基础查询
PostGIS 基础查询 数据库维护 ps aux | grep postgrespsql 使用命令登录数据库psql -U postgres -d testdb -h localhost -p 5432postgres用户名,testdb数据库名称,localhost ip地址,可以省略,5432端口,可以省略。 …...
Shell错误:/bin/bash^M: bad interpreter: No such file or directory
目录 错误原因和现象 解决方案 错误原因和现象 在执行shell脚本的时候,报错:/bin/bash^M: bad interpreter: No such file or directory。 是由于该脚本文件是在Windows平台编写,然后在MacOS平台中执行。 在Windows平台上文件是dos格式&…...

Golang之路---01 Golang的安装与配置
Golang之路—01 Golang语言安装与配置 官网上下载Windows环境下的安装包 官网下载地址 双击下载后的文件进行安装,可根据需要自定义选择解压后的文件位置。 接着新创建一个文件夹,保存Golang语言项目。 在里面新建bin,pkg,src三个文件夹。 环境变量…...
Anolis OS 8.8服务器采用docker容器方式搭建gerrit3.8.1服务
采用docker容器方式搭建gerrit3.8.1服务 一、选择管理帐户密码的方式二、部署gerrit服务1. 采用docker compose部署单服务的方式部分gerrit(1) docker-compose.yaml文件内容(2) 在docker-compose.yaml文件所在目录调用下面命令先进行初始化操作 2. 在宿主机上部署httpd服务用于…...
PyTorch 中的多 GPU 训练和梯度累积作为替代方案
动动发财的小手,点个赞吧! 在本文[1]中,我们将首先了解数据并行(DP)和分布式数据并行(DDP)算法之间的差异,然后我们将解释什么是梯度累积(GA),最后…...

Appium+python自动化(三十五)- 命令启动appium之 appium服务命令行参数(超详解)
简介 前边介绍的都是通过按钮点击启动按钮来启动appium服务,有的小伙伴或者童鞋们乍一听可能不信,或者会问如何通过命令行启动appium服务呢?且听一一道来。 一睹为快 其实相当的简单,不看不知道,一看吓一跳…...

vmware的window中安装GNS3
1.向vmware中的windows虚拟机传送文件 点击虚拟机-安装VMwaretools 安装在虚拟机上面 此图标代表已经成功,将文件复制到虚拟机上里面 2.安装 安装gns3,需要先安装winpcap(检查网卡)和wireshark(对winpcap上数据进行抓…...

FPGA XDMA 中断模式实现 PCIE3.0 AD7606采集 提供2套工程源码和QT上位机源码
目录 1、前言2、我已有的PCIE方案3、PCIE理论4、总体设计思路和方案AD7606数据采集和缓存XDMA简介XDMA中断模式QT上位机及其源码 5、vivado工程1--BRAM缓存6、vivado工程2--DDR4缓存7、上板调试验证8、福利:工程代码的获取 1、前言 PCIE(PCI Express&am…...

某某大学某学院后台Phar反序列化GetShell
觉得这个洞还算有点意思,可以记录一下 首先在另一个二级学院进行目录扫描时发现源码www.rar,并且通过一些页面测试推测这两个二级学院应该是使用了同一套CMS 分析源码,发现使用的是ThinkPHP 5.1.34 LTS框架 通过APP、Public得到后台访问路径…...

【ChatGPT辅助学Rust | 基础系列 | 基础语法】变量,数据类型,运算符,控制流
文章目录 简介:一,变量1,变量的定义2,变量的可变性3,变量的隐藏 二、数据类型1,标量类型2,复合类型 三,运算符1,算术运算符2,比较运算符3,逻辑运算…...

使用云服务器和Frp(快速反向代理)框架快速部署实现内网穿透
目录 一. 背景1.1 内网穿透1.2 Frp介绍1.3 Frp配置流程 二. 云服务器配置2.1 配置安全组2.2 编写frps.ini 三. 内网主机配置3.1 编辑frpc.ini文件3.2 启动服务并配置开机自启动 四. 参考文献 一. 背景 现在有一台ubuntu云服务器,我想通过内网穿透将一台内网的主机当…...
Mac 上使用 Tesseract OCR 识别图片文本
Tesseract OCR 引擎:Tesseract是一个开源的OCR引擎,你需要先安装它。可以从Tesseract官方网站(https://github.com/tesseract-ocr/tesseract)下载适用于你的操作系统的安装程序或源代码,并按照官方文档进行安装。 Tes…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

npm安装electron下载太慢,导致报错
npm安装electron下载太慢,导致报错 背景 想学习electron框架做个桌面应用,卡在了安装依赖(无语了)。。。一开始以为node版本或者npm版本太低问题,调整版本后还是报错。偶尔执行install命令后,可以开始下载…...