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

蓝桥杯每日真题 - 第18天

题目:(出差)

题目描述(13届 C&C++ B组E题)

解题思路:

  • 问题分析

    • 问题实质是一个带权图的最短路径问题,但路径的权重包含两个部分:

      1. 从当前城市到下一个城市的路程时间。

      2. 当前城市的离开时间。

    • 需要计算从城市1到城市N的最短时间。

  • 图的表示

    • 用邻接矩阵表示图,将不存在的边初始化为无穷大。

  • 路径规划

    • 使用Dijkstra算法,从城市1开始,动态更新到其他城市的最短路径时间。

  • 特殊处理

    • 起点城市(城市1)的离开时间staytime[0]设为0,因为小明可以直接出发。

  • 时间复杂度

    • Dijkstra的时间复杂度为 O(N2)O(N^2)O(N2) (由于使用邻接矩阵实现),在节点数较小时仍然可行。

代码实现(C语言):

#define maxn 1001
#define inf INT_MAX
#define edgetype int#include <stdio.h>
#include <stdlib.h>
#include <limits.h>void initedges(edgetype graph[maxn][maxn], int n)
{int i, j;for (i = 0; i < n; i++){for (j = 0; j < n; j++){graph[i][j] = inf;}}
}void addedges(edgetype graph[maxn][maxn], int u, int v, int w)
{if (graph[u][v] == inf || w < graph[u][v]){graph[u][v] = w;}if (graph[v][u] == inf || w < graph[v][u]){graph[v][u] = w;}
}void dijkstra(edgetype graph[maxn][maxn], int s, int n, edgetype dist[maxn], edgetype staytime[maxn])
{int visited[maxn];int i;for (i = 0; i < n; i++){dist[i] = inf;visited[i] = 0;}dist[s] = 0;while (1){int minindex = -1;int min = inf;for (int i = 0; i < n; i++){if (!visited[i] && dist[i] < min) {min = dist[i];minindex = i;}}if (min == inf){break;}visited[minindex] = 1;for (i = 0; i < n; i++){int u = graph[minindex][i];if (visited[i]){continue;}if (u == inf){continue;}if (dist[i] == inf || dist[i] > min + u + staytime[i]){dist[i] = min + u + staytime[i];}}}
}int main(int argc, char *argv[])
{int N, M, i, u, v, w;edgetype staytime[maxn], graph[maxn][maxn], dist[maxn];scanf("%d %d", &N, &M);for (i = 0; i < N; i++){scanf("%d", &staytime[i]);}staytime[0] = 0;initedges(graph, N);for (i = 0; i < M; i++){scanf("%d %d %d", &u, &v, &w);addedges(graph, u - 1, v - 1, w);}dijkstra(graph, 0, N, dist, staytime);printf("%d", dist[N - 1] - staytime[N - 1]);return 0;
}

得到运行结果:

代码分析: 

  • 图的初始化

    • initedges 函数将图中所有的边权值初始化为无穷大(inf),表示没有直接连通的路径。

  • 添加边

    • addedges 函数会将边(u, v)及其权值w加入到邻接矩阵中,同时判断是否已有更短路径,如果有就更新。

  • Dijkstra算法

    • 核心部分是 dijkstra 函数:

      • 使用一个 visited 数组标记已确定最短路径的节点。

      • 每次找到当前未访问节点中距离起点最近的节点。

      • 松弛操作:尝试更新所有相邻节点的最短距离,考虑路径花费和目标节点的离开时间。

  • 输入输出

    • 输入部分:城市数量N、道路数量M、每个城市离开时间以及M条双向边信息。

    • 输出部分:从起点城市1到终点城市N的最短时间。

  • 重要逻辑

    • dijkstra 中更新距离时,将离开时间加入权值计算:dist[i] = min + u + staytime[i]

难度分析

⭐️⭐️⭐️⭐️⭐️难难难难难急急急急急急急

总结

本代码解决了一个加权图中的特殊最短路径问题,考虑到离开时间的影响。
它适用于小型的城市网络,提供了可靠的解法。

相关文章:

蓝桥杯每日真题 - 第18天

题目&#xff1a;&#xff08;出差&#xff09; 题目描述&#xff08;13届 C&C B组E题&#xff09; 解题思路&#xff1a; 问题分析 问题实质是一个带权图的最短路径问题&#xff0c;但路径的权重包含两个部分&#xff1a; 从当前城市到下一个城市的路程时间。 当前城市的…...

MySQL中索引全详解

第一部分&#xff1a;什么是索引 索引在数据库中就像书的目录&#xff0c;能够快速定位数据位置&#xff0c;从而提升查询效率。没有索引时&#xff0c;数据库查询需要从头到尾扫描整个表&#xff08;称为全表扫描&#xff09;&#xff0c;这在数据量大时非常耗时。有了索引后&…...

探索复合物TPP-PEG-Heparin的特性;磷酸三苯酯-聚乙二醇-肝素的线粒体靶向性

TPP-PEG-Heparin&#xff0c;即磷酸三苯酯&#xff08;TPP&#xff09;、聚乙二醇&#xff08;PEG&#xff09;和肝素&#xff08;Heparin&#xff09;的复合物&#xff0c;其特性融合了这三种成分的性质。 一、线粒体靶向性 TPP部分&#xff1a;具有线粒体靶向功能&#xf…...

ubuntu 配置 多个 git 客户端 账户

Git配置两个或多个账户 https://blog.csdn.net/mainking2003/article/details/134711865 git 提交 不用输入用户名、密码的方法&#xff08;GIT免密提交&#xff09; https://blog.csdn.net/wowocpp/article/details/125797263 git config 用法 https://blog.csdn.net/blueb…...

Web3与智能合约:区块链技术下的数字信任体系

随着互联网的不断发展&#xff0c;Web3代表着我们迈入了一个去中心化、更加安全和智能的网络时代。作为Web3的核心组成部分&#xff0c;区块链技术为智能合约的出现和发展提供了强有力的基础。智能合约不仅仅是自动化的代码&#xff0c;它们正逐步成为重塑数字世界信任体系的关…...

RocketMQ文件刷盘机制深度解析与Java模拟实现

引言 在现代分布式系统中&#xff0c;消息队列&#xff08;Message Queue, MQ&#xff09;作为一种重要的中间件&#xff0c;扮演着连接不同服务、实现异步通信和消息解耦的关键角色。Apache RocketMQ作为一款高性能的分布式消息中间件&#xff0c;广泛应用于实时数据流处理、…...

高级编程之结构化代码

背景&#xff1a;以下没结构化代码之前&#xff0c;定时器同步店铺信息的代码。 结构化的思想&#xff1a;SRP&#xff08;单一职责&#xff09;&#xff0c;一个方法是做一件事&#xff0c;层次是相关的&#xff0c;逻辑和数据操作进行拆分&#xff0c;数据操作从业务流程上定…...

学习编程,学习中间件,学习源码的思路

01 看的多&#xff0c;内化不足 最近想复习一下编程相关的知识&#xff0c;在复习前我翻开了之前的一些笔记&#xff0c;这些笔记基本都是从书本、视频、博客等摘取记录的&#xff0c;看着这些笔记心里总结&#xff1a;看的多&#xff0c;内化不足。 02 整理大纲 为了解决这个…...

网络安全与加密

1.Base64简单说明描述&#xff1a;Base64可以成为密码学的基石&#xff0c;非常重要。特点&#xff1a;可以将任意的二进制数据进行Base64编码结果&#xff1a;所有的数据都能被编码为并只用65个字符就能表示的文本文件。65字符&#xff1a;A~Z a~z 0~9 / 对文件进行base64编码…...

开源协议介绍

文章目录 1. MIT License2. Apache License 2.03. GNU General Public License (GPL)4. GNU Lesser General Public License (LGPL)5. BSD License6. Mozilla Public License (MPL)7. Creative Commons Licenses (CC)8. Unlicense选择建议 在 开源平台上&#xff0c;开源项目通…...

Java技术复习提升 10异常

10 异常 10.1异常介绍及分类 异常捕获 选中后alttabt->选中try-catch 异常就是程序执行中不正常的情况 注意语法和逻辑错误并不是异常 异常分类有两种 error和exception error是错误 虚拟机无法解决的严重问题 exception是其他因为编程错误或者外在因素导致的一般性的问…...

java版工程项目管理系统源码:Spring Cloud与前后端分离的完美结合

在现代化的工程项目管理中&#xff0c;一套功能全面、操作便捷的系统至关重要。本文将介绍一个基于Spring Cloud和Spring Boot技术的Java版工程项目管理系统&#xff0c;结合Vue和ElementUI实现前后端分离。该系统涵盖了项目管理、合同管理、预警管理、竣工管理、质量管理等多个…...

Oracle与MySQL中CONCAT()函数的使用差异

一、CONCAT函数介绍 CONCAT函数是MySQL等数据库中用于连接两个或多个字符串的内置函数。其基本语法如下&#xff1a; CONCAT(string1, string2, ...)参数说明&#xff1a; string1, string2, …&#xff1a;需要连接的字符串参数&#xff0c;可以有多个。 返回值&#xff1…...

AI社媒引流工具:解锁智能化营销的新未来

在数字化浪潮的推动下&#xff0c;社交媒体成为品牌营销的主战场。然而&#xff0c;面对海量的用户数据和日益复杂的运营需求&#xff0c;传统营销方法显得力不从心。AI社媒引流王应运而生&#xff0c;帮助企业在多平台中精准触达目标用户&#xff0c;提升营销效率和效果。 1.…...

浏览器的事件循环机制

一、请简述浏览器的事件循环机制&#xff08;Event Loop&#xff09;基本原理 浏览器的事件循环机制是用于协调处理 JavaScript 中的异步任务与同步任务执行顺序的一种机制&#xff0c;它确保了代码能够按照合理的顺序执行&#xff0c;避免阻塞页面渲染等情况。其基本原理如下…...

如何在 React 项目中应用 TypeScript?应该注意那些点?结合实际项目示例及代码进行讲解!

在 React 项目中应用 TypeScript 是提升开发效率、增强代码可维护性和可读性的好方法。TypeScript 提供了静态类型检查、自动补全和代码提示等功能&#xff0c;这对于 React 开发者来说&#xff0c;能够帮助早期发现潜在的 bug&#xff0c;提高开发体验。 1. 项目初始化 在现…...

排序算法(五)--归并排序

文章目录 引言归并排序概述C语言实现代码解析结论 归并排序 C语言实例 引言 归并排序&#xff08;Merge Sort&#xff09;作为一种经典的排序算法&#xff0c;以其稳定性、分治法的巧妙应用以及相对高效的时间复杂度而著称。 归并排序概述 归并排序采用分治法&#xff08;Di…...

Linux KASLR 地址偏移

kaslr开启时地址 cat /proc/cmdline BOOT_IMAGE/boot/vmlinuz-5.4.0-193-generic rootUUID0e46dee3-4557-434a-a2d2-a35c6ad3d327 ro find_preseed/preseed.cfg auto noprompt prioritycritical localeen_US quiet cat /boot/config-$(uname -r) | grep CONFIG_RANDOMIZE_B…...

利用开源图床的技巧与实践

随着互联网的普及&#xff0c;图片的使用变得越来越广泛。无论是个人博客、社交媒体还是企业网站&#xff0c;都离不开图片的呈现。而图床作为图片存储和管理的工具&#xff0c;可以帮助开发者和内容创作者高效地管理图片资源。本文将探讨如何利用开源图床&#xff0c;并提供相…...

Unity Lua方向的面试真题详解

最近有位同学面试Unity&#xff0c;面试的公司采用Lua的方案来做公司项目&#xff0c;我们把面试时问道的真题列举出来&#xff0c;并配上参考回复。 1、Lua热更文件时&#xff0c;文件是重写的&#xff0c;还是只写一部分? 热更分为资源更新和代码更新&#xff0c;资源更新…...

经验笔记:Git 基础操作指南

推荐一下Gitee最好的Git操作教程&#xff1a;Learn Git Branching 经验笔记&#xff1a;Git 基础操作指南 1. 安装 Git 首先确保您的计算机上已安装 Git。如果还没有安装&#xff0c;可以从 Git官网 下载并安装。 2. 配置 Git 安装完成后&#xff0c;打开命令行工具&#…...

大模型在智能客服中心领域的应用思考

大模型在智能客服中心领域的应用思考 作者&#xff1a;开源呼叫中心系统 FreeIPCC&#xff0c;Github地址&#xff1a;https://github.com/lihaiya/freeipcc 随着人工智能技术的飞速发展&#xff0c;特别是深度学习技术的突破&#xff0c;大型语言模型&#xff08;LLMs&#x…...

ssm旅游推荐系统的设计与开发

摘 要 旅游推荐系统是一个综合性的在线旅游推荐平台&#xff0c;旨在为用户提供便捷的旅游规划和预定服务。通过该系统&#xff0c;用户能够浏览各类景点信息并进行分类查找&#xff0c;同时获取详尽的景点介绍和相关照片&#xff0c;以辅助做出旅行决策。系统提供在线门票订购…...

C++从零到满绩——入门基础and类和对象(上)

目录 1>>前言 2>>函数重载 3>>引用 3.1>>引用的概念 3.2>>引用三大特性 3.3>>引用的使用 3.4>>const引用 3.5>>指针与引用的关系 4>>inline内联函数 5>>nullptr 6>>类和对象&#xff08;上&#…...

如何为PDF文件创建口令密码

介绍Adobe Acrobat https://helpx.adobe.com/cn/acrobat/using/access-acrobat-across-web-mobile-desktop.html 使用Adobe Acrobat软件添加口令...

【ubuntu】开机进入initramfs,无法开机

Step 1 blkid查看 ext4 的磁盘 Step 2 找到TYPE"EXT4"的盘&#xff0c;我们此处是 /dev/mapper/ubuntu–vg-ubuntu–lv,fsck命令是用于检查和修复Linux文件系统中的错误。通过使用-t参数指定文件系统类型&#xff08;例如ext4&#xff09;。我们使用如下命令进行…...

java基础---反射

仅供个人学习使用 1. 什么是反射 Java反射机制是在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够知道这个类的所有属性和方法&#xff1b;对于任意一个对象&#xff0c;都能够调用它的任意方法和属性&#xff1b;这种动态获取信息以及动态调用对象方法的功能称为…...

CircuitBreaker机制详解:Elasticsearch中的资源管理

CircuitBreaker机制详解:Elasticsearch中的资源管理 在现代软件架构中,熔断器(CircuitBreaker)是一种重要的模式,用于防止系统过载并保护系统稳定性。在Elasticsearch中,熔断器机制尤其关键,因为它们帮助管理资源使用,防止节点因资源耗尽而崩溃。本文将深入探讨Elasti…...

毕氏完美数

毕达哥拉斯 概要 2 \sqrt{2} 2 ​ a b , a < b , a > b ab,a<b,a>b ab,a<b,a>b 判断完美数验证 自守数验证 水仙花数代码验证 概要 回顾完美数&#xff0c;自守数&#xff0c;水仙花数&#xff0c;根号2感受最美公式。 2 \sqrt{2} 2 ​ 毕达哥拉斯创立了一…...

数据结构-8.Java. 七大排序算法(中篇)

本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 中篇主要实现后三种排序算法: 冒泡排序,快速排序,下一篇讲 归并排序. 文章专栏: Java-数据结构 若有问题 评论区见 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作…...

如何能让安全责任更清晰——构建清晰安全责任体系策略与实践

安全已成为各行各业不可忽视的重要议题。然而&#xff0c;要确保组织的安全运行&#xff0c;仅仅有安全意识是不够的&#xff0c;还需要有一套清晰明确的安全责任体系来支撑。这套体系能够明确每个人的安全职责&#xff0c;促进安全管理工作的有序进行&#xff0c;降低事故发生…...

VBA技术资料MF228:移动形状并覆盖某单元格区域

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…...

《Python基础》之基本数据类型

目录 基本数据类型 1、Number(数字) &#xff08;1&#xff09;、整数&#xff08;int&#xff09; &#xff08;2&#xff09;、浮点数&#xff08;float&#xff09; &#xff08;3&#xff09;、复数&#xff08;complex&#xff09; &#xff08;4&#xff09;、 布尔…...

2024 APMCM亚太数学建模C题 - 宠物行业及相关产业的发展分析和策略(详细解题思路)

在当下&#xff0c; 日益发展的时代&#xff0c;宠物的数量应该均为稳步上升&#xff0c;在美国出现了下降的趋势&#xff0c; 中国 2019-2020 年也下降&#xff0c;这部分变化可能与疫情相关。需要对该部分进行必要的解释说明。 问题 1: 基于附件 1 中的数据及您的团队收集的…...

66 mysql 的 表自增长锁

前言 mysql 的表锁之 AUTO_INC, 是我们自增长的时候做并发控制的锁 主要是用于 自增长生成新的 id 的时候的控制 在前面的文档中, 我们又看到 mysql 这边自增长的处理的相关的大概脉络 但是 对于一些 并发控制的细节, 我们当时 应该是直接忽略掉了 我们这里就来看一下…...

java中的this关键字

&#x1f389;&#x1f389;&#x1f389;欢迎来到我的博客,我是一名自学了2年半前端的大一学生,熟悉的技术是JavaScript与Vue.目前正在往全栈方向前进, 如果我的博客给您带来了帮助欢迎您关注我,我将会持续不断的更新文章!!!&#x1f64f;&#x1f64f;&#x1f64f; 文章目录…...

资源控制器--laravel进阶篇

laravel的控制器当中有个资源控制器,这个比较好用。 创建资源控制器 php artisan make:controller PhotoController --resource 创建个路由来使用该资源控制器 use App\Http\Controllers\PhotoController; Route::resource(photos, PhotoController::class); 隐式模型绑定不…...

智能工厂的设计软件 为了监管控一体化的全能Supervisor 的监督学习 之 序7 进化论及科学的信息技术创新:分布式账本/区块链/智能合约

Q&A Q46、 聊聊“分布式账本”“区块链”和“智能合约” “分布式账本”、“区块链”和“智能合约”是现代信息技术领域的几个重要概念&#xff0c;它们在金融、供应链管理、物联网等多个领域都发挥着重要作用。以下是对这三个概念的详细解析&#xff1a; 分布式账本 …...

从零开始认识显卡

显卡&#xff08;GPU&#xff0c;全称为Graphics Processing Unit&#xff09;&#xff0c;是电脑中专门负责图形处理的硬件组件。以下是从零开始认识显卡的简单介绍&#xff1a; 1. 显卡的基本组成 显卡通常由以下几个主要部分组成&#xff1a; GPU核心&#xff1a;显卡的“…...

什么是计算机网络

什么是计算机网络&#xff1f; 计算机网络的定义计算机网络的分类按覆盖范围分类按拓扑结构分类按通信传输介质分类按信号频带占用方式分类 计算机网络的功能信息交换资源共享分布式处理 计算机网络的组成计算机网络的定义计算机网络的分类按覆盖范围分类按拓扑结构分类按通信传…...

网络安全在线网站/靶场:全面探索与实践

目录 1. CyberPatriot 简介 功能与特点 适用人群 2. Hack The Box 简介 功能与特点 适用人群 3. OverTheWire 简介 功能与特点 适用人群 4. VulnHub 简介 功能与特点 适用人群 5. PortSwigger Web Security Academy 简介 功能与特点 适用人群 6. TryHackM…...

多旋翼无人机长航时远距离集群技术详解

多旋翼无人机长航时远距离集群技术是当前无人机技术发展的重要方向之一&#xff0c;它结合了多旋翼无人机的灵活性和集群技术的优势&#xff0c;实现了无人机在长时间、远距离条件下的高效协同作业。以下是对该技术的详细解析&#xff1a; 一、多旋翼无人机特点 多旋翼无人机以…...

C#编写的日志记录组件 - 开源研究系列文章

以前编写过一个日志记录组件的博文&#xff0c;这次发布一个修改过的完善版本。 1、 项目目录&#xff1b; 2、 源码介绍&#xff1b; 1) 实现&#xff1b; 2) 使用&#xff1b; 后面的参数为级别设置&#xff0c;只有大于这个级别的才进行日志记录&#xff0c;限制了日志记录的…...

使用 Java 操作 SQLite 数据库

文章目录 1.导入依赖2.实际应用 1.导入依赖 <dependencies><dependency><groupId>org.xerial</groupId><artifactId>sqlite-jdbc</artifactId><version>3.36.0.3</version></dependency> </dependencies>2.实际应…...

再次讨论下孤注一掷

在孤注一掷中的黑客技术里面&#xff0c;简单介绍了电影孤注一掷中用的一些"黑科技"&#xff0c;这里继续讨论下&#xff0c;抛弃这些黑科技&#xff0c;即使在绝对公平的情况下&#xff0c;你也一样赢不了赌场 相对论有一个假设就是光速不变&#xff0c;这里也有个…...

系统思考—跳出症状看全局

感谢合作伙伴的邀请&#xff0c;圆满结束国药试剂关于《系统思考》的课程。课堂上&#xff0c;我们围绕“缺货”这个看似具体的问题&#xff0c;展开了一场跨部门的深度探讨。销售、采购、物流等部门各抒己见&#xff0c;发现每个部门的出发点都是为了公司好&#xff0c;但误判…...

前端面试vue篇:Vue2 和 Vue3 在设计和性能上有显著区别

Vue3 相对于 Vue2 的主要改进和性能提升体现在以下几个关键领域 1.响应式系统&#xff1a; (1)Vue2 使用 Object.defineProperty 遍历对象的所有属性来实现响应式&#xff0c;这在大型应用中可能导致性能瓶颈&#xff0c;尤其是在组件初次渲染和大量数据变化时。 (2)Vue3 引入了…...

每天五分钟深度学习:神经网络模型的直观理解

本文重点 神经网络是深度学习的基础模型之一,本文将讲解一下基础模型神经网络是什么? 神经网络 如上所示,这个神经网络有两层(我们认为输入层不算神经网络的层数),其中一个隐藏层,还有一个是输出层。我们称隐藏层为第一层,输出层为第二层,输入层为第零层。 我们有输…...

高集成的MCU方案已成电机应用趋势?

【哔哥哔特导读】高集成化的芯片成为当下MCU领域研发和市场布局的重点&#xff0c;但是在实际应用中仍然面临散热等痛点问题&#xff0c;MCU厂商是如何解决和优化这些痛点&#xff1f; 随着全球工业自动化、智能制造和绿色发展的不断推进&#xff0c;中国电机行业正站在新一轮…...

商用密码产品认证名录说明

《商用密码产品认证目录》是为贯彻落实《中华人民共和国密码法》&#xff0c;进一步健全完善商用密码产品认证体系&#xff0c;更好满足商用密码产业发展需要&#xff0c;根据《国家密码管理局 市场监管总局关于调整商用密码产品管理方式的公告》《市场监管总局 国家密码管理局…...