单源最短路问题
全部代码
全部代码在github acwing 上
正在更新
https://github.com/stolendance/acwing
图论
欢迎大家star与fork

单源最短路问题 先用spfa算法 不行再换其他的
spfa-超级万能 说不定比dijsktra还快
dis[] 代表第k到某一点的最短距离
queue 代表刚被更新的点 它有可能更新其他路径 所以检查它的出边
isin代表该点是否在queue中
队列放入起点 <-k
while(队列不为空)取出队头遍历所有t的出边 t-w>b如果dis[b]>dis[t]+w[t,b],更新,如果b不在队列中,加入b

typedef long long ll;
typedef pair<ll,ll> pll;
struct Edge
{int next;int val;Edge(int next_,int val_):next(next_),val(val_){;}
};
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<Edge> > graph(n+1);for(auto item:times){int a=item[0];int b=item[1];int c=item[2];graph[a].push_back(Edge(b,c));}vector<ll> dis(graph.size(),INT_MAX);vector<int> isin(graph.size(),0);queue<int> ls;ls.push(k);dis[k]=0;isin[k]=1;while(ls.size()){int t=ls.front();ls.pop();isin[t]=0;for(int i=0;i<graph[t].size();i++){// k->t->idint distance=graph[t][i].val;int id=graph[t][i].next;if(dis[t]+distance<dis[id]){dis[id]=dis[t]+distance;if(isin[id]==0){ls.push(id);isin[id]=1;}}}}int rs= *max_element(dis.begin()+1,dis.end());if(rs==INT_MAX) return -1;else return rs;}
};
朴素版dijsktra -单源最短路-所有边权重都是正数 基于 稠密图(邻接矩阵)
s:当前已经确定最短路径距离的点
-
dis[0 ]=0 dis[i]=+OO 只有起点被确定到了
-
for(i 1 …n)
t《- 不在s中的距离最近的点
s〈-t
用t更新其他点的距离(看下)
dij实现的时候是通过 将距离设置成无穷大 来表达 不可达
dij 由于边很多, 稠密图 所以用邻接矩阵存即可
dij 需要找n个点 所以外层是一个for循环x
总结下来:1. 把未加入的最近的加进来2. 标记加入3. 根据加入的点更新距离

#include<iostream>
#include<vector>
using namespace std;
#define INA INT_MAX
//https://leetcode.cn/problems/network-delay-time/
int networkDelayTime(vector<vector<int> >& times, int N, int k) {// 因为点的坐标是从1开始 , 所以开N+1个// 直接在graph上更新 方便很多// graph要采用long long INT_MAX+某个数 不会变成负数vector<vector<long long> > graph(N+1,vector<long long>(N+1,INT_MAX));for(int i=1;i<=N;i++) graph[i][i]=0;for(auto e:times) graph[e[0]][e[1]]=e[2];vector<int> vis(graph.size(),0);vis[k]=1;// 只要找下除了起点的接下来的点for(int i=1;i<graph.size()-1;i++){int minid=0,minx=INA;// 在没有使用过的检查最短的距离for(int j=1;j<graph.size();j++){if(vis[j]==0&&graph[k][j]<minx){minid=j;minx=graph[k][j];}}vis[minid]=1;// 更新// 根据这个点更新其他所有距离for(int j=1;j<graph.size();j++){graph[k][j]=min(graph[k][j],graph[k][minid]+ graph[minid][j]);}}int ans=0;for(int i=1;i< graph.size();i++){if(graph[k][i]==INT_MAX) return -1;ans=max(ans, (int)graph[k][i]);}return ans;
}
int main()
{vector<vector<int> > times={{2,1,1},{2,3,1},{3,4,1}};int rs=networkDelayTime(times,4,2);cout<<rs<<endl;}
dijstra 稀疏图(邻接表) -我更喜欢的方式!!!
求点k到其他点的距离
与上面不同的情况是, 采用邻接表+最小堆
最小堆 的格式是(点k到该点的距离,该点的id)
dis[] 存储的是点k到达每个点的最短距离
st[] 存储的是否能确定点k到达每个点的距离while(队列不为空)
{队列弹出一个如果该点确定了最短距离,就不管它 if(st[]) continue把弹出的这个点加入最短距离根据这个点进行扩展,遍历这个点指向其他点的边如果比div小,则更新距离加入队列中
}


typedef long long ll;
typedef pair<ll,ll> pll;
struct Edge
{int next;int val;Edge(int next_,int val_):next(next_),val(val_){;}
};
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<Edge> > graph(n+1);for(auto item:times){int a=item[0];int b=item[1];int c=item[2];graph[a].push_back(Edge(b,c));}vector<ll> dis(graph.size(),INT_MAX);vector<int> st(graph.size(),0);priority_queue<pll,vector<pll>,greater<pll> > ls;ls.push(pll(0,k));dis[k]=0;while(ls.size()){auto item=ls.top();ls.pop();ll distance=item.first;int id=item.second;// 保证未加入if(st[id]) continue;// 加入st[id]=1;// 扩展更新for(int i=0;i<graph[id].size();i++){// k->id->id2// distance distance2int id2=graph[id][i].next;int distance2=graph[id][i].val;if(distance+distance2<dis[id2]){dis[id2]=distance+distance2;// 加入队列ls.push(pll(dis[id2],id2));}}}int rs=(int)*max_element(dis.begin()+1,dis.end());if(rs==INT_MAX) return -1;else return rs;}
};
相关文章:
单源最短路问题
全部代码 全部代码在github acwing 上 正在更新 https://github.com/stolendance/acwing 图论 欢迎大家star与fork 单源最短路问题 先用spfa算法 不行再换其他的 spfa-超级万能 说不定比dijsktra还快 dis[] 代表第k到某一点的最短距离 queue 代表刚被更新的点 它有可能更…...
Security方法注解权限控制过程及自定义权限表达式
文章目录 使用内置的权限表达式PreAuthorizePermissionEvaluator 自定义权限表达式SysMethodSecurityExpressionHandler源码流程 SysMethodSecurityExpressionRoot 使用内置的权限表达式 PreAuthorize 这个用来判断超级管理员的话,还得在表达式上加上或 Permissi…...
vue 省市县三级联动
1、 <template><div>所在省<el-select popper-class"eloption" :popper-append-to-body"true"change"getShiList(obj.province)" v-model"obj.province" placeholder"请选择所在省" clearableclear"re…...
ChatGPT实现编程语言转换
编程语言转换 对于程序员来说,往往有一类工作,是需要将一部分业务逻辑实现从服务端转移到客户端,或者从客户端转移到服务端。这类工作,通常需要将一种编程语言的代码转换成另一种编程语言的代码,这就需要承担这项工作…...
浅拷贝和深拷贝
浅拷贝: 定义:浅拷贝(Shallow Copy)是一种简单的对象复制方式,将一个对象的数据成员直接复制给另一个对象(通常是通过默认的复制构造函数或赋值运算符实现),这些数据成员可以是基本…...
进程地址空间与页表方面知识点(缺页中断及写时拷贝部分原理)
谢谢阅读,如有错误请大佬留言!! 目录 谢谢阅读,如有错误请大佬留言!! 抛出总结 开始介绍 发现问题 进程地址空间(虚拟地址) 页表 物理内存与进程地址空间映射 缺页中断基本…...
Photoshop如何使用滤镜之实例演示?
文章目录 0.引言1.将普通照片制作成油画效果2.使用液化滤镜修出完美身材3.用镜头光晕滤镜制作唯美的逆光人像4.用Camera Raw滤镜对偏色风景照进行调色 0.引言 因科研等多场景需要进行绘图处理,笔者对PS进行了学习,本文通过《Photoshop2021入门教程》及其…...
Flutter 组件抽取:日期(DatePicker)、时间(TimePicker)弹窗选择器【仿照】
简介 仿照《Flutter 仿ios自定义一个DatePicker》实行的日期弹窗选择器(DatePicker)、时间弹窗选择器(TimePicker) 效果 范例 class _TestPageState extends State<TestPage> {overridevoid initState() {super.initStat…...
基于opencv的YOLOV3对图片的目标检测
目录 1. 准备工作 2. utils 函数 2.1 plot_show 函数 2.2 get_prediction 函数 2.3 draw_bounding_box 绘制边界框函数...
Mermaid流程图
所有流程图都由节点,几何形状和边缘,箭头或线条组成。mermaid代码定义了这些节点和边缘的制作和交互方式。 它还可以容纳不同的箭头类型、多方向箭头以及与子图之间的链接。 1、流程图的方向 TB - 从上到下TD - 自上而下/与上到下相同BT - 从下到上RL -…...
国产!全志科技T507-H工业核心板( 4核ARM Cortex-A5)规格书
1核心板简介 创龙科技 SOM-TLT507 是一款基于全志科技 T507-H 处理器设计的 4 核 ARM Cortex-A 53 全国产工业核心板,主频高达 1.416GHz 。核心板 CPU 、ROM 、RAM、电源、晶振等所有元器件均采用国产工业级方案,国产化率 100%。 核心板通过邮票孔连接方式引出 MIPI CSI 、…...
java小记 2023-05-05
public class Test {/*** 谓类的方法就是指类中用static 修饰的方法(非static 为实例方法),比如main 方法,那么可以以main* 方法为例,可直接调用其他类方法,必须通过实例调用实例方法,this 关键…...
CentOS安装Nginx
准备工作 在安装Nginx之前,我们需要进行一些准备工作: 确认系统是否已经安装了Nginx。如果已经安装了,需要卸载掉旧版本。安装EPEL源,以获取Nginx的软件包。安装必要的依赖软件包。 卸载旧版Nginx 如果已经安装了旧版本的Ngin…...
CSS布局基础(CSS书写顺序 导航栏写法 常见问题)
CSS布局基础(CSS书写顺序 & 导航栏写法) CSS布局基础(CSS书写顺序)导航栏写法PC端网页开发一般步骤容易出问题的点 CSS布局基础(CSS书写顺序) 布局定位属性自身属性(宽高,边框&…...
打造卓越 QML 层级设计:从入门到精通
目录标题 引言:QML 层级设计的重要性1.1 什么是 QML1.2 层级设计的核心理念1.3 实际应用案例 QML 基础知识2.1 语言概述2.2 基本元素2.3 属性和信号 设计原则与规范3.1 命名规范3.1.1 标识符命名3.1.2 文件命名3.1.3 文件夹命名 3.2 代码风格3.2.1 缩进与空格3.2.2 …...
shell流程控制之条件判断练习
1、判断当前磁盘剩余空间是否有20G,如果小于20G,则将报警邮件发送给管理员,每天检查一次磁盘剩余空间。 因为如果磁盘剩余空间小于20G需要报警发送邮件给管理员,所以需要对管理员的邮箱进行设置 (1)首先…...
linux中TF启动卡制作:磁盘分区文件同步
文章目录 前言:1. 连接TF卡2. 磁盘卸载载与分区2.1 磁盘卸载2.2 创建第一个分区2.3 创建第二个分区 3. 磁盘格式化4. 文件同步5. 检查与BOOT分区启动文件拷贝总结: 前言: TF卡在linux环境下配置好相关软件后,把配置好的系统以及软…...
【操作系统OS】学习笔记:第一章 操作系统基础【哈工大李治军老师】
基于本人观看学习 哈工大李治军老师主讲的操作系统课程 所做的笔记,仅进行交流分享。 特此鸣谢李治军老师,操作系统的神作! 如果本篇笔记帮助到了你,还请点赞 关注 支持一下 ♡>𖥦<)!! 主页专栏有更多࿰…...
Linux C/C++ 网络编程中地址格式转换(inet_pton和inet_ntop函数)
网络编程中地址格式转换(inet_pton和inet_ntop函数) 地址格式转换 #include <sys/types.h> #include <sys/socket.h> #include <arpa/inet.h>int inet_pton(int af , const char * src ,void * dst);(1…...
庖丁解牛函数知识---C语言《2》
目录 前言: 1.嵌套调用函数 2.链式访问 3.函数的声明与定义 4.*递归 5.递归与非递归 ❤博主CSDN:啊苏要学习 ▶专栏分类:C语言◀ C语言的学习,是为我们今后学习其它语言打好基础,C生万物! 开始我们的C语言之旅吧…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
