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

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...