当前位置: 首页 > 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...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...