【Dijkstra单源最短路径解法】蓝桥杯2022年第十三届决赛真题-出差

我也来贡献一份题解:Dijkstra单源最短路径的简单变式【简单C代码】


这道题的前置知识的Dijkstra单源最短路径算法

如果还没学过,建议去看AcWing算法教程的**图论(2)**中最短路径问题的讲解,u1s1–y总讲的是真的通透!

思路

这道题和单源最短路径唯一的区别就是,多了一个隔离时间,我们可以将所有的隔离时间都加到路径上,也就是直接将问题转化成单源最短路径问题即可~

同时不要忘记所有的路都是双向的,所以在建图的时候,别忘记双向建图,否则没分!

例如:这是题目所给的测试用例

在这里插入图片描述

我们可以将它转化为我们熟悉的单源最短路径问题,只要做一个简单的处理即可,然后就可以套用Dijkstra算法的万能模板:

[1] --11-- [2]
 |			|
 8			7
 |			|
[3] -- 9 -- [4]

让所有的点的 前边 加上这个点的等待时间作为新的

代码

#include <iostream>
#include <cstring>
#define int long long 
using namespace std;

const int N = 1001;		
int g[N][N], dist[N], wait[N];	//g为邻接矩阵 
bool st[N];	  			//表示结点是否已经确定最短路径 
int n, m;				//n为结点数量,m为边数量 

inline void Dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;		//从第一个结点到达第一个结点的最短路径为 0 
	for (int i = 0; i < n - 1; i++ ) {	//循环 n 次处理 n 个结点 
		int t = -1;
		for (int j = 1; j <= n; j++ ) {
			if (!st[j] && (t == -1 || dist[j] < dist[t])) {	//第一次会选择找到的第一个边然后去找最短的边 
				t = j;	//寻找没有确定最短路径的点当中 到第一个点最近的点 
			}
		}
		//找到没有确定的最近的点
		for (int j = 1; j <= n; j++) {
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}//从第一个最近的点开始向后更新最短路径 
		st[t] = true;	//将确定好最短路径的点设置为true表示已经确定了最短路径 
	}
	cout << dist[n] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++ ) {
		cin >> wait[i];
	}
	wait[1] = wait[n] = 0;
	
	memset(g, 0x3f, sizeof g);
	for (int i = 0; i < m; i++ ) {
		int u, v, c;
		cin >> u >> v >> c;
		g[u][v] = wait[v] + c;	//无重边的情况,如果有重边需要进行取重边的最小值 
		g[v][u] = wait[u] + c;
	}
	
	Dijkstra();
} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/536246.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

IJKPLAYER源码分析-iOS端显示

1 简介 1.1 EAGL(Embedded Apple Graphics Library) 与Android系统使用EGL连接OpenGL ES与原生窗口进行surface输出类似&#xff0c;iOS则用EAGL将CAEAGLLayer作为OpenGL ES输出目标。 与 Android EGL 不同的是&#xff0c;iOS EAGL 不会让应用直接向 BackendFrameBuffer 和 F…

Socks5代理IP如何获取?如何使用?

当我们在互联网上浏览网页、下载文件或者进行在线活动时&#xff0c;隐私和安全问题常常被提及。在这样的环境下&#xff0c;一个有效的解决方案是使用Sock5IP。本教程将向您介绍Sock5IP的使用方法&#xff0c;帮助您保护个人隐私并提升网络安全。 一、什么是Sock5IP&#xff1…

Elasticsearch部署安装

环境准备 Anolis OS 8 Firewall关闭状态&#xff0c;端口自行处理 Elasticsearch&#xff1a;7.16.1&#xff08;该版本需要jdk11&#xff09; JDK&#xff1a;11.0.19 JDK # 解压 tar -zxvf jdk-11.0.19_linux-x64_bin.tar.gz# 编辑/etc/profile vim /etc/profile# 加入如下…

Linux内核之Binder驱动红黑树:rb_root用法实例(四十四)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

SpringBoot - Logback 打印第三方 Jar 日志解决方案

问题描述 最近碰到一个很苦恼的问题&#xff0c;就是第三方的 Jar 在自己项目里日志可以正常输出&#xff0c;但是一旦被引用到其他项目里&#xff0c;就日志死活打不出来…… 解决方案 这是原来的配置 - logback.xml <?xml version"1.0" encoding"UTF-8…

【JavaScript】DOM编程-什么是事件

今天几号 实现效果&#xff1a; 在这个示例中我们的事件三要素都是什么呢&#xff1f; &#xff08;1&#xff09;事件源&#xff0c;事件被触发的对象 谁&#xff1a;按钮 &#xff08;2&#xff09;事件类型&#xff0c;如何触发&#xff0c;什么事件&#xff0c;比如鼠标…

SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测

SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测 目录 SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测预测效果基本介绍模型描述程…

详解小度Wi-Fi内部芯片及电路原理图分析

小度随身WiFi是一款便携式USB路由器&#xff0c;它实现了用户跨终端联网&#xff0c;随身携带&#xff0c;可以在室内实现免费WiFi覆盖。外形美观&#xff0c;小巧便携。 这一款小度WiFi采用的主芯片是MT7601UN&#xff0c;一款高度集成的Wi-Fi单芯片&#xff0c;支持150 Mbp…

Java工具类:批量发送邮件(带附件)

​ 不好用请移至评论区揍我 原创代码&#xff0c;请勿转载&#xff0c;谢谢&#xff01; 一、介绍 用于给用户发送特定的邮件内容&#xff0c;支持附件、批量发送邮箱账号必须要开启 SMTP 服务&#xff08;具体见下文教程&#xff09;本文邮箱设置示例以”网易邮箱“为例&…

PyTorch-Lightning:trining_step的自动优化

文章目录 PyTorch-Lightning&#xff1a;trining_step的自动优化总结&#xff1a; class _ AutomaticOptimization()def rundef _make_closuredef _training_stepclass ClosureResult():def from_training_step_output class Closure PyTorch-Lightning&#xff1a;trining_ste…

嵌入式单片机入职第二天-EEPROM与IIC

上午&#xff1a; 1.安装Jlink驱动&#xff0c;死活没反应&#xff0c;因为昨天才装完系统&#xff0c;领导让我装电脑主板驱动 领导方法进惠普官网通过查询电脑型号&#xff0c;里面几十个驱动搞得我眼花&#xff0c;领导告诉我进官网就去开会了&#xff0c;可能因为是外网&…

Win11 WSL2 install Ubuntu20.04 and Seismic Unix

Win11系统&#xff0c;先启用或关闭Windows功能&#xff0c;勾选“适用于Linux的Windows子系统”和“虚拟机平台”两项 设置wsl默认版本为wsl2&#xff0c;并更新 wsl --list --verbose # 查看安装版本及内容 wsl --set-default-version 2 # 设置wsl默认版本为wsl2 # 已安装…

nvm安装详细教程(安装nvm、node、npm、cnpm、yarn及环境变量配置)

一、安装nvm 1. 下载nvm 点击 网盘下载 进行下载 2、双击下载好的 nvm-1.1.12-setup.zip 文件 3.双击 nvm-setup.exe 开始安装 4. 选择我接受&#xff0c;然后点击next 5.选择nvm安装路径&#xff0c;路径名称不要有空格&#xff0c;然后点击next 6.node.js安装路径&#…

智慧矿山视频智能监控与安全监管方案

一、行业背景 随着全球能源需求的日益增长&#xff0c;矿业行业作为国民经济的重要支柱&#xff0c;其发展日益受到广泛关注。然而&#xff0c;传统矿山管理模式的局限性逐渐显现&#xff0c;如生产安全、人员监管、风险预警等方面的问题日益突出。因此&#xff0c;智慧矿山智…

【算法练习】30:快速排序学习笔记

一、快速排序的算法思想 原理&#xff1a;快速排序基于分治策略。它的基本思想是选择一个元素作为“基准”&#xff0c;将待排序序列划分为两个子序列&#xff0c;使得左边的子序列中的所有元素都小于基准&#xff0c;右边的子序列中的所有元素都大于基准。这个划分操作被称为分…

【Python函数和类3/6】函数的返回值

目录 知识回顾 目标 函数的返回值 Tips 练习 ​编辑return的其它特性 任意类型的返回值 返回多个值 return的位置 小结 局部变量 局部变量的作用域 全局变量 全局变量的作用域 同名变量 pi的作用域 总结 知识回顾 在上篇博客中&#xff0c;我们学习给函数设置参…

集群开发学习(一)(安装GO和MySQL,K8S基础概念)

完成gin小任务 参考文档&#xff1a; https://www.kancloud.cn/jiajunxi/ginweb100/1801414 https://github.com/hanjialeOK/going 最终代码地址&#xff1a;https://github.com/qinliangql/gin_mini_test.git 学习 1.安装go wget https://dl.google.com/go/go1.20.2.linu…

玩机进阶教程------手机定制机 定制系统 解除系统安装软件限制的一些步骤解析

定制机 在于各工作室与商家合作定制rom中有一些定制机。限制用户私自安装第三方软件。或者限制解锁 。无法如正常机登陆账号等等。定制机一般用于固定行业或者一些部门。专机专用。例如很多巴枪扫描机型等等。或者一些小牌机型。对于没有官方包的机型首先要导出各个分区来制作…

【OpenVINO™】使用 OpenVINO™ C# API 部署 YOLOv9 目标检测和实例分割模型(上篇)

YOLOv9模型是YOLO系列实时目标检测算法中的最新版本&#xff0c;代表着该系列在准确性、速度和效率方面的又一次重大飞跃。它通过引入先进的深度学习技术和创新的架构设计&#xff0c;如通用ELAN&#xff08;GELAN&#xff09;和可编程梯度信息&#xff08;PGI&#xff09;&…

复合数据类型

在C语言中&#xff0c;复合数据类型是指那些可以包含多个简单数据类型的数据类型。以下是一些常见的C语言复合数据类型以及相关的例子&#xff1a; 1. 数组&#xff08;Arrays&#xff09;&#xff1a; 数组是一种可以存储多个相同类型数据的数据结构。例如&#xff1a; #in…