当前位置: 首页 > 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;但是更多的还是程序员需要…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...