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

Dijkstra(求最短路)

时间复杂是 O(n2+m) ,n 表示点数,m 表示边数

模板(朴素法一般m等于n^2的时候使用)

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=510;
int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定int Dijkstra()
{memset(dist, 0x3f,sizeof dist); //初始化距离  0x3f代表无限大dist[1]=0;                      //第一个点到自身的距离为0for(int i=0;i<n;i++)            //有n个点所以要进行n次 迭代{int t=-1;                   //t存储当前访问的点for(int j=1;j<=n;j++)       //这里的j代表的是从1号点开始if(!st[j]&&(t==-1||dist[t]>dist[j]))     t=j;st[t]=true;   //找到了距离最小的点t,并用最小的点t去更新其他的点到起点的距离for(int j=1;j<=n;j++)dist[j]=min(dist[j],dist[t]+g[t][j]);}if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径return dist[n];
}
int main()
{cin>>n>>m;memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径//所以每个点初始为无限大while(m--){int x,y,z;cin>>x>>y>>z;g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边}cout<<Dijkstra()<<endl;return 0;
}

模板(堆优化版一般在m等于n的时候使用)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;   //堆里储存距离和编号
const int N=1e6+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx;  //对于每个点k,开一个单链表,存储K所有可以走到的点,h[k]存储这个单链表的头节点 
int dist[N];  //存储距离
bool st[N];    //储存状态//添加一条a到b的边 
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; }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 ver=t.second,distance=t.first; if(st[ver])continue; //如果该点已经确定,则跳过该点st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i])//更新ver所指向的节点距离{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]; 
}int main(){cin>>n>>m;memset(h,-1,sizeof h);while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z);}cout<<Dijkstra()<<endl;return 0;
} 

相关文章:

Dijkstra(求最短路)

时间复杂是 O(n2m) &#xff0c;n 表示点数&#xff0c;m 表示边数 模板(朴素法一般m等于n^2的时候使用) #include<bits/stdc.h> #include<algorithm> using namespace std; const int N510; int g[N][N]; //为稠密阵所以用邻接矩阵存储 int dist[N]; //用…...

React 脚手架

1.React 定义 React 脚手架&#xff08;React boilerplate&#xff09;是一种预先设置好的、可以快速启动 React 项目的工具。脚手架已经包含了 React、Webpack、Babel、ESLint、Jest 等一些常用的工具和库&#xff0c;并已经配置好了这些工具的参数&#xff0c;可以直接使用和…...

CTFSHOW php命令执行

目录 web29 过滤flag web30 过滤system php web31 过滤 cat|sort|shell|\. 这里有一个新姿势 可以学习一下 web32 过滤 &#xff1b; . web33 web34 web35 web36 web37 data伪协议 web38 短开表达式 web39 web40 __FILE__命令的扩展 web41 web42 重定向…...

侧滑置顶,取消置顶

第一步:布局 <?xml version"1.0" encoding"utf-8"?> <com.ddmh.magic.camera.ui.widget.SwipeMenuLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"…...

Pycharm解决启动时候索引慢的问题

设置里去掉update里面的两个勾 shared indexes中&#xff0c;把自动下载索引改成不下载使用本地索引...

Http请求响应时间一般划分标准

HTTP请求的响应时间被认为是长或短通常取决于具体应用场景和性能需求。一般来说&#xff0c;以下是一些常见的对HTTP请求响应时间进行划分的标准&#xff1a; 即时响应&#xff1a;通常在毫秒级别的响应时间被认为是即时响应。这适用于对实时性要求较高的应用&#xff0c;如实时…...

生成测试报告,在Unittest框架中就是简单

测试套件&#xff08;Test Suite&#xff09;是测试用例、测试套件或两者的集合&#xff0c;用于组装一组要运行的测试&#xff08;多个测试用例集合在一起&#xff09;。 &#xff08;1&#xff09;创建一个测试套件&#xff1a; import unittest suite unittest.TestSuite…...

生成式人工智能的潜在有害影响与未来之路(一)

这是本文的第1版&#xff0c;反映了截至2023年5月15日&#xff0c;Generative AI的已记载的和预期的危害。由于Generative AI的发展、使用和危害的快速变化&#xff0c;我们承认这是一篇内在的动态论文&#xff0c;未来会发生变化。 在本文中&#xff0c;我们使用一种标准格式…...

lightdb23.3 表名与包名不能重复

LightDB 表名与包名不能重复 从 LightDB 23.3 版本开始表名和包名不能重复&#xff0c;与 oracle 一致。原先已已支持包名和schema名不能重复。 背景 在之前版本在同一schema 下可以创建相同名字的表和包。这会导致在存储过程中使用%type指定变量类型时&#xff0c;如果存在…...

Oracle 开发篇+Java通过HiKariCP访问Oracle数据库

标签&#xff1a;HikariCP、数据库连接池、JDBC连接池、释义&#xff1a;HikariCP 是一个高性能的 JDBC 连接池组件&#xff0c;号称性能最好的后起之秀&#xff0c;是一个基于BoneCP做了不少的改进和优化的高性能JDBC连接池。 ★ Java代码 import java.sql.Connection; impor…...

进销存管理系统(小杨国贸)springboot采购仓库财务java jsp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 进销存管理系统&#xff08;小杨国贸&#xff09;spri…...

指针初阶(2)

文章目录 5. 指针和数组6. 二级指针7. 指针数组 附&#xff1a; 5. 指针和数组 指针变量&#xff1a;指针变量就是指针变量&#xff0c;不是数组&#xff0c;指针变量的大小是4/8个字节&#xff0c;专门是用来存放地址的。 数组&#xff1a;数组就是数组&#xff0c;不是指针&a…...

基于Gradio的GPT聊天程序

网上很多别人写的&#xff0c;要用账号也不放心。就自己写了一个基于gradio的聊天界面&#xff0c;部署后可以本地运行。 特点&#xff1a; 可以用openai的&#xff0c;也可以用api2d&#xff0c;其他api可以自己测试一下。使用了langchain的库 可以更改模型&#xff0c;会的…...

包管理工具详解npm 、 yarn 、 cnpm 、 npx 、 pnpm(2023)

1、包管理工具npm &#xff08;1&#xff09;包管理工具npm&#xff1a; Node Package Manager&#xff0c;也就是Node包管理器&#xff1b;但是目前已经不仅仅是Node包管理器了&#xff0c;在前端项目中我们也在使用它来管理依赖的包&#xff1b;比如vue、vue-router、vuex、…...

Terraform 系列-批量创建资源时如何根据某个字段判断是否创建

系列文章 Terraform 系列文章Grafana 系列文章 概述 前文 Grafana 系列 - Grafana Terraform Provider 基础 介绍了使用 Grafana Terraform Provider 创建 Datasource. 这几天碰到这么一个现实需求&#xff1a; 使用 Terraform 批量创建日志数据源时, 有的数据源类型是 El…...

Android侧滑栏(一)可缩放可一起移动的侧滑栏

在实际的各类App开发中&#xff0c;经常会需要做一个左侧的侧滑栏&#xff0c;类似于QQ这种。 今天这篇文章总结下自己在开发中遇到的这类可以跟随移动且可以缩放的侧滑栏。 一、实现原理 使用 HorizontalScrollView 实现一个水平方向的可滑动的View&#xff0c;左布局为侧滑…...

简单程度与自负是否相关?探索STM32的学习价值

事实上&#xff0c;无论STM32是否简单并不重要&#xff0c;更重要的是我们能通过学习STM32获得什么。通过STM32&#xff0c;我们可以学习到许多知识&#xff1a;如果我们制作一个键盘或鼠标&#xff0c;我们可以学习USB协议。如果我们制作一个联网设备&#xff0c;我们需要学习…...

第二章:CSS基础进阶-part3:弹性例子布局

文章目录 Flex盒模型二、常见属性2.1 flex属性2.2 justify-content2.3 flex-wrap2.4 flex-flow2.5 align-items2.6 父容器-align-content Flex盒模型 1、普通盒模型 2、弹性盒布局 使用弹性盒布局能让容器的宽度跟随浏览器窗口的变化而变换 二、常见属性 2.1 flex属性 2.2 …...

函数与方法有区别?

有区别&#xff0c;当然是有区别。 不管是java、rust还是go&#xff0c;他们都是不一样的。 先看定义&#xff1a; 函数&#xff08;Function&#xff09; 是一段独立的代码块&#xff0c;用于执行特定的任务。函数可以被多次调用&#xff0c;并且可以接受参数和返回结果。在G…...

VMware vCenter忘记密码操作,和Linus原理一致

mount -o remount,rw / passwd root ## 修改 root 密码要选择对应账户## 输入新密码&#xff0c;再输入一次新密码 umount / ## 卸载根文件系统 reboot -f ## 重新引导 vCenter...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...