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

Dijkstra求最短路 I

题目

给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出−1。

输入格式:

第一行包含整数n和m。

接下来m行,每行包含三个整数 x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式:

输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出−1。

数据范围:

1≤n≤500,1≤m≤(10)^5,图中涉及边长均不超过10000。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

题解

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
//g[x][y]表示节点x指向节点y的权值,也可表示不存在
int g[N][N];
//dist[n]表示源点到节点n的距离
int dist[N];
//表示state,当值为true时,表示该节点为最优路径,也可理解为标记该节点为最优
bool st[N];int dijkstra(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;//每次循环都标记一个最优节点路径for (int i = 0; i < n - 1; i ++ ) {int t = -1;//确定该t值为未标记节点中的最短值,即确定一个最优节点路径for (int j = 1; j <= n; j++){if (!st[j] && (t == -1 || dist[t] > dist[j])) {t = j;}}//扩展该t值最优节点的临近节点for (int j = 1; j <= n; j ++ ) {dist[j] = min(dist[j], dist[t] + g[t][j]);}st[t] = true;}if (dist[n] == 0x3f3f3f3f) {return -1;}return dist[n];
}int main(){scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof g);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);}printf("%d\n", dijkstra());return 0;
}

相关文章:

Dijkstra求最短路 I

题目 给定一个n个点m条边的有向图&#xff0c;图中可能存在重边和自环&#xff0c;所有边权均为正值。 请你求出1号点到n号点的最短距离&#xff0c;如果无法从1号点走到n号点&#xff0c;则输出−1。 输入格式&#xff1a; 第一行包含整数n和m。 接下来m行&#xff0c;每…...

复习单向,双向链表,并且实现两种链表的增加和删除功能。

单链表头插 Linklist insert_head(datatype element,Linklist head) {//创建新节点 Linklist screate_node();if(NULLs)return head; s->dataelement;//1,判断链表为空if(NULLhead){heads;}else //链表不为空{s->nexthead;heads;}return head; } 单链表尾插 Linklist …...

【webpack】技巧使用

webpack和TypeScript 安装webpack相关内容安装TS相关内容配置初始化数据初始化运行展示和目录展示报错解决&#xff08;缺失文件配置&#xff09; 安装前端必备神奇lodash测试一下entry配置index.html模板配置修改打包出来的index.html的titleinject注入chunks 属性多页面配置 …...

windows 谷歌浏览器Chrome 怎么禁止更新

1.首先把任务管理器里的谷歌浏览器程序结束&#xff1a; &#xff08;鼠标在任务栏右击&#xff0c;出现任务管理器&#xff09; 2.windowr&#xff0c;输入services.msc 带有Google Update的服务&#xff0c;选择禁用。 3.windowr&#xff0c;输入taskschd.msc 任务计划程序…...

力扣(leetcode)第349题两个数组的交集(Python)

349.两个数组的交集 题目链接&#xff1a;349.两个数组的交集 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出…...

python Flask 写一个简易的 web 端程序(附demo)

python Flask 写一个简易的 web 端程序 &#xff08;附demo&#xff09; 介绍简单介绍装饰器 app.route("/") 进阶增加接口设置端口 静态网页核心代码完整代码 介绍 Flask 是一个用于构建 Web 应用程序的轻量级 Python Web 框架。它设计简单、易于学习和使用&#x…...

mysql问题

面试官&#xff1a;MySQL中&#xff0c;如何定位慢查询? 候选人&#xff1a; 嗯~&#xff0c;我们当时做压测的时候有的接口非常的慢&#xff0c;接口的响应时间超过了2秒以上&#xff0c;因为我们当时的系统部署了运维的监控系统Skywalking &#xff0c;在展示的报表中可以看…...

iframe通信,window.postMessage父子项目数据通信

父 > 子 父项目 <iframe:src"cockpitUrl"id"cockpitIframe"load"handleLoad" ></iframe>// 向子系统传递数据&#xff08;注意要再iframe的load中注册&#xff0c;保证iframe已经加载完成&#xff0c;这样子项目才能监听到&…...

ES6中新增Array.from()函数的用法详解

目录 Map对象的转换 Set对象的转换 字符串的转换 类数组对象的转换 Array.from可以接受三个参数 ES6为Array增加了from函数用来将其他对象转换成数组。当然&#xff0c;其他对象也是有要求&#xff0c;也不是所有的&#xff0c;可以将两种对象转换成数组。 1、部署了Iter…...

Camera2+OpenGL ES+MediaCodec+AudioRecord实现录制音视频写入H264 SEI数据

记录一下学习过程&#xff0c;得到一个需求是基于Camera2OpenGL ESMediaCodecAudioRecord实现录制音视频。 需求&#xff1a; 在每一帧视频数据中&#xff0c;写入SEI额外数据&#xff0c;方便后期解码时获得每一帧中的自定义数据。点击录制功能后&#xff0c;录制的是前N秒至…...

C语言笔试题之反转链表(头插法)

实例要求&#xff1a; 1、给定单链表的头节点 head &#xff1b;2、请反转链表&#xff1b;3、最后返回反转后的链表&#xff1b; 案例展示&#xff1a; 实例分析&#xff1a; 1、入参合理性检查&#xff0c;即head ! NULL || head->next ! NULL&#xff1b;2、while循环…...

WEB3:互联网发展的新时代

随着科技的飞速发展&#xff0c;互联网已从最初的信息交流平台发展为涵盖了工作、生活、娱乐、教育等众多领域的复杂系统。我们将其称之为“WEB3”&#xff0c;这个名称是对互联网新时代的高度概括&#xff0c;标志着我们已经迈入了WEB3时代。 在WEB3时代&#xff0c;互联网将…...

c语言:贪吃蛇的实现

目录 贪吃蛇实现的技术前提&#xff1a; Win32 API介绍 控制台程序&#xff08;console&#xff09; 控制台屏幕上的坐标 GetStdHandle GetConsoleCursorInfo CONSOLE_CURSOR_INFO SetConsoleCursorInfo SetConsoleCursorPosition GetAsyncKeyState 宽字符的打印 …...

第5课 使用FFmpeg将rtmp流再转推到rtmp服务器

本课对应源文件下载链接&#xff1a; https://download.csdn.net/download/XiBuQiuChong/88801992 通过前面的学习&#xff0c;我们已经可以正常播放网络rtmp流及本地mp4文件。这节课&#xff0c;我们将在前面的基础上实现一个常用的转推功能&#xff1a;读取rtmp流或mp4文件并…...

Vue中v-if和v-show区别

Vue中v-if和v-show是两个常用的指令&#xff0c;用于控制元素的显示和隐藏。虽然它们都能达到相同的效果&#xff0c;但在实现机制和使用场景上有一些区别。本文将详细介绍v-if和v-show的区别&#xff0c;并且通过示例代码来演示它们的使用。 首先&#xff0c;让我们来看一下v…...

LabVIEW与EtherCAT实现风洞安全联锁及状态监测

LabVIEW与EtherCAT实现风洞安全联锁及状态监测 在现代风洞试验中&#xff0c;安全联锁与状态监测系统发挥着至关重要的作用&#xff0c;确保了试验过程的安全性与高效性。介绍了一套基于EtherCAT总线技术和LabVIEW软件开发的风洞安全联锁及状态监测系统。该系统通过实时、可靠…...

PostgreSQL的wal文件回收问题

引子 将PostgreSQL的GUC参数wal_recycle设置为on&#xff0c;然后对数据库执行一定业务量的操作&#xff0c;会发现在pg_wal目录下&#xff0c;有很多未来使用的wal文件&#xff0c;且创建时间比现在正在使用的wal文件更早&#xff0c;下文将描述和分析这种情况。 问题描述 …...

java-JUC并发编程学习笔记05(尚硅谷)

我们写一段测试代码: 会出现线程不安全的问题。 使用Vector解决线程不安全问题&#xff1a; 但是这个类几乎不会被使用了&#xff0c;因为效率太低。 方法二&#xff1a;通过Collections解决&#xff1a; 但是这种方案实际中也不太会使用。 我们还有第三种方法使用CopyOnWri…...

vulhub中spring的CVE-2022-22947漏洞复现

Spring Cloud Gateway是Spring中的一个API网关。其3.1.0及3.0.6版本&#xff08;包含&#xff09;以前存在一处SpEL表达式注入漏洞&#xff0c;当攻击者可以访问Actuator API的情况下&#xff0c;将可以利用该漏洞执行任意命令。 参考链接&#xff1a; https://tanzu.vmware.c…...

网络原理TCP/IP(1)

文章目录 端口号UDP协议 在网络通信中&#xff0c;协议非常重要 协议进行了分层 应用层就是对应着应用程序&#xff0c;是程序员打交道最多的这一层&#xff0c;调用系统提供的网络api写出来的代码都是属于应用层的 应用层有很多现成的协议&#xff0c;但是更多的还是程序员需要…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...