备战蓝桥杯---图论之最短路dijkstra算法

目录

先分个类吧:

1.对于有向无环图,我们直接拓扑排序,和AOE网类似,把取max改成min即可。

2.边权全部相等,直接BFS即可

3.单源点最短路

从一个点出发,到达其他顶点的最短路长度。

Dijkstra算法:用于一个节点到所有其他节点的最短路。(要求:不存在负权边,可以用于无向图)


先分个类吧

1.对于有向无环图,我们直接拓扑排序,和AOE网类似,把取max改成min即可

2.边权全部相等,直接BFS即可

3.单源点最短路

从一个点出发,到达其他顶点的最短路长度。

基本操作:松弛:d[u]+w<d[v],于是距离更改。

Dijkstra算法:用于一个节点到所有其他节点的最短路。(要求:不存在负权边,可以用于无向图)

具体过程:

1.开始之前,认为所有点都未计算,dis[]全部赋为极大值。

2.源点的dis[]=0;

3。计算与源点相邻的所有点的dis=map[s][v];

4.在还未算出最短路点的dis中选出最小一个点u,显然,因为不存在负权边,它的最短路就是dis.

5.对于与u相连的所有点v若dis[u]+map[u][v]比当前的dis小就松弛更新。

6.重复上述4,5操作。

正确性证明:

其实就是每一次贪心,显然,从源点开始的第一步得到的最短的路肯定就是最短路(到它的其他路肯定比它长)。

当我们把除源点外第一个确定的加入后,我们再用它去更新一下它连的点。

然后,我们选其中最小的点,它就是确定的。因为,要走到它,要么从那些没有确定最小路的点出发到它(因为这点是最小的点+无负权边,因此这样的点距离肯定更大),要么从已经确定的点上拓展出来,又因为他们不断地更新松弛(每一个确定最小路的点加入后,我们再用它去更新一下它连的点),所以我们可以保证在已经确定地点到最小的点的路径是最优的。因此,我们保证最小的点它就是确定的。

下面放一道模板题:

下面是AC代码(注意,无向边建图edge要2倍):

#include<bits/stdc++.h>
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
void merge(int x,int y,int v){edge[++cnt].zhi=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
priority_queue<ty> q;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].zhi){dis[i1]=dis[ck.dian]+edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cin>>n>>m1>>s>>t;memset(head,-1,sizeof(head));for(int i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]=0;cout<<dij(s,t);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/258001.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

UI文件原理

使用UI文件创建界面很轻松很便捷&#xff0c;他的原理就是每次我们保存UI文件的时候&#xff0c;QtCreator就自动帮我们将UI文件翻译成C的图形界面创建代码。可以通过以下步骤查看代码 到工程编译目录&#xff0c;一般就是工程同级目录下会生成另一个编译目录&#xff0c;会找到…

rbd快照管理、rbd快照克隆原理与实现、rbd镜像开机自动挂载、ceph文件系统、对象存储、配置对象存储客户端、访问Dashboard

目录 快照 快照克隆 开机自动挂载 ceph文件系统 使用MDS 对象存储 配置服务器端 配置客户端 访问Dashborad 快照 快照可以保存某一时间点时的状态数据快照是映像在特定时间点的只读逻辑副本希望回到以前的一个状态&#xff0c;可以恢复快照使用镜像、快照综合示例 #…

【刷题记录】合并两个有序数组、移除元素

本系列博客为个人刷题思路分享&#xff0c;有需要借鉴即可。 1.题目链接&#xff1a; T1&#xff1a;LINK T2&#xff1a;LINK 2.详解思路&#xff1a; T1: 思路1&#xff1a;弄个新数组&#xff0c;比较两个数组中的值&#xff0c;哪个小就把哪个值放到新数组中。 分析1&a…

自定义类型详解 结构体,位段,枚举,联合

目录 结构体 1.不完全声明 2.结构体的自引用 3.定义与初始化 4.结构体内存对齐与结构体类型的大小 结构体嵌套问题 位段 1.什么是位段&#xff1f; 2.位段的内存分配 枚举 1.枚举类型的定义 2.枚举的优点 联合&#xff08;共同体&#xff09; 1.联合体类型的声明以…

Vue语法

1.vue模板语法2大类 插值语法&#xff1a; 功能&#xff1a;用于解析标签内容 用途&#xff1a;用于标签内容定义 写法&#xff1a;{{xxx}}&#xff0c;xxx是js表达式&#xff0c;且可以直接读取到data中的所有属性 指令语法&#xff1a; 功能&#xff1a;用于解析标签&am…

去空行小工具Html + Javascript

这是一个平常用到的小工具&#xff0c;为了节省屏幕空间把空行去掉&#xff0c;怕要用的时候找不到故记录在此。 效果图 网页版&#xff0c;放在浏览器里就可以用 <!doctype html> <html><head><meta charset"utf-8"><title>去回车…

JMeter性能测试系列一初识JMeter

1.JMeter介绍 Apache组织的Stefano Mazzocchi是JMeter项目的创始人。编写JMeter最初的目的是为了测试server的性能(后期被Tomcat替代)。随后&#xff0c;JMeter在Apache组织内部开始被其他项目所使用&#xff0c;并最终推广出来&#xff0c;成为独立的软件项目并不断更新&…

内网渗透Searchall敏感凭证信息搜索工具

一、开发背景 在实战中进入内网的时候&#xff0c;大家需要搜集一些敏感信息例如账号&#xff0c;密码甚至浏览器的账号密码。searchall完美解决了这个问题。所以我就结合自身的经验写了一款搜索敏感信息的利用工具。它可以搜索敏感信息&#xff0c;更快为你获取到有价值的信息…

【51单片机】LED点阵屏(江科大)

9.1LED点阵屏 1.LED点阵屏介绍 LED点阵屏由若干个独立的LED组成,LED以矩阵的形式排列,以灯珠亮灭来显示文字、图片、视频等。 2.LED点阵屏工作原理 LED点阵屏的结构类似于数码管,只不过是数码管把每一列的像素以“8”字型排列而已。原理图如下 每一行的阳极连在一起,每一列…

Codeforces Round 926 (Div. 2)(A,B,C,D,E,F)

这场还是很有含金量的&#xff0c;B题开始就有难度了&#xff0c;B是个推结论的题&#xff0c;C要推结论然后递推&#xff0c;D题是有点难的树上DP&#xff08;主要是状态转移方程不好写&#xff09;&#xff0c;E题是个二进制预处理然后状压DP&#xff0c;F题是个数论&#xf…

【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…

python系统学习Day2

section3 python Foudamentals part one&#xff1a;data types and variables 数据类型&#xff1a;整数、浮点数、字符串、布尔值、空值 #整型&#xff0c;没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型&#xff…

红队笔记Day2 -->上线不出网机器

今天就来讲一下在企业攻防中如何上线不出网的机器&#xff01;&#xff01; 1.基本网络拓扑 基本的网络拓扑就是这样 以下是对应得的P信息&#xff0c;其中的52网段充当一个内网的网段&#xff0c;而111充当公网网段 先ping一下&#xff0c;确保外网ping不通内网&#xff0c;内…

2024年道路运输企业主要负责人证模拟考试题库及道路运输企业主要负责人理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年道路运输企业主要负责人证模拟考试题库及道路运输企业主要负责人理论考试试题是由安全生产模拟考试一点通提供&#xff0c;道路运输企业主要负责人证模拟考试题库是根据道路运输企业主要负责人最新版教材&#…

你知道.NET的字符串在内存中是如何存储的吗?

一、字符串对象的内存布局 从“值类型”和“引用类型”来划分&#xff0c;字符串自然属于引用类型的范畴&#xff0c;所以一个字符串对象自然采用引用类型的内存布局。引用类型实例的内存布局总的来说整个内存布局分三块&#xff1a;ObjHeader TypeHandle Payload。对于一般…

EasyCaptcha,开源图形验证码新标杆!

引言&#xff1a; 随着互联网的普及&#xff0c;验证码已成为网站和应用程序中不可或缺的安全组件。它能够有效地防止自动化攻击、垃圾邮件和机器人活动。在众多验证码解决方案中&#xff0c;Easy-captcha以其简单易用和高度可定制的特点受到了开发者的青睐。本文将指导读者如…

浅谈业务场景中缓存的使用

浅谈缓存 一、背景二、缓存分类1.本地缓存2.分布式缓存 三、缓存读写模式1.读请求2.写请求 四、缓存穿透1.缓存空对象2.请求校验3.请求来源限制4.布隆过滤器 五、缓存击穿1.改变过期时间2.串行访问数据库 六、缓存雪崩1.避免集中过期2.提前更新缓存 七、缓存与数据库一致性1.设…

【MySQL】学习约束和使用图形化界面创建表

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-iqtbME2KmWpQFQSt {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…

java.lang.NoClassDefFoundError: org/springframework/core/GenericTypeResolver

前言 小编我将用CSDN记录软件开发求学之路上亲身所得与所学的心得与知识&#xff0c;有兴趣的小伙伴可以关注一下&#xff01; 也许一个人独行&#xff0c;可以走的很快&#xff0c;但是一群人结伴而行&#xff0c;才能走的更远&#xff01;让我们在成长的道路上互相学习&…

BUGKU-WEB GET

题目描述 没有提示&#xff0c;就一个get&#xff0c;启动场景看看&#xff1a; 解题思路 显然是PHP语言解读分析代码吧写出你的payload 相关工具 略 解题步骤 进入场景分析代码 $what$_GET[what]; echo $what; if($whatflag) echo flag{****};前两句&#xff1a;使用get…