蓝桥杯每日真题 - 第18天
题目:(出差)
题目描述(13届 C&C++ B组E题)


解题思路:
-
问题分析
-
问题实质是一个带权图的最短路径问题,但路径的权重包含两个部分:
-
从当前城市到下一个城市的路程时间。
-
当前城市的离开时间。
-
-
需要计算从城市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天
题目:(出差) 题目描述(13届 C&C B组E题) 解题思路: 问题分析 问题实质是一个带权图的最短路径问题,但路径的权重包含两个部分: 从当前城市到下一个城市的路程时间。 当前城市的…...
HTTP 协议应用场景
一、HTTP 协议简介 HTTP(Hypertext Transfer Protocol)即超文本传输协议,是用于分布式、协作式和超媒体信息系统的应用层协议,是互联网数据通信的基础。它采用客户端 - 服务器(Client-Server)的通信模式&am…...
【Linux庖丁解牛】—Linux基本指令(下)!
目录 1、grep指令 2、zip/unzip指令 3、sz/rz指令 4、tar指令 编辑 5、scp指令 6、bc指令 7、uname –r指令 8、重要的几个热键 9、关机 10、完结撒花 1、grep指令 grep是文本过滤器,其作用是在指定的文件中过滤出包含你指定字符串的内容,…...
python: generator model using sql server 2019
設計或生成好數據庫,可以生成自己設計好的框架項目 # encoding: utf-8 # 版权所有 :2024 ©涂聚文有限公司 # 许可信息查看 :言語成了邀功盡責的功臣,還需要行爲每日來值班嗎 # 描述: : 生成实体 # Author …...
Kafka怎么发送JAVA对象并在消费者端解析出JAVA对象--示例
1、在pom.xml中加入依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-stream-kafka</artifactId><version>3.1.6</version></dependency> 2、配置application.yml 加入Kafk…...
深度学习(1)
一、torch的安装 基于直接设备情况,选择合适的torch版本,有显卡的建议安装GPU版本,可以通过nvidia-smi命令来查看显卡驱动的版本,在官网中根据cuda版本,选择合适的版本号,下面是安装示例代码 GPUÿ…...
golang 嵌入式armv7l压缩编译打包
编译 Go 应用程序 go build -ldflags"-s -w" -o myapp.exe . 使用 UPX 压缩可执行文件(window下载并设置环境变量) upx --best --lzma myapp.exe 可从10M压缩到1M 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 …...
Makefile 之 join
join $(join <list1>,<list2> ) 名称:连接函数——join。 功能:把<list2>中的单词对应地加到<list1>的单词后面。如果<list1>的单词个数要比<list2>的多, 那么,<list1>中的多出…...
集合卡尔曼滤波(Ensemble Kalman Filter),用于二维滤波(模拟平面上的目标跟踪),MATLAB代码
集合卡尔曼滤波(Ensemble Kalman Filter) 文章目录 引言理论基础卡尔曼滤波集合卡尔曼滤波初始化预测步骤更新步骤卡尔曼增益更新集合 MATLAB 实现运行结果3. 应用领域结论 引言 集合卡尔曼滤波(Ensemble Kalman Filter, EnKF)是…...
北京申请中级职称流程(2024年)
想找个完整详细点的申请流程资料真不容易,做个分享送给需要的人吧。 不清楚为什么说文章过度宣传,把链接和页面去掉了,网上自己找一下。 最好用windows自带的EDGE浏览器打开申请网站,只有在开始申请的时间内才可以进行网上申报&…...
ubuntu.24安装cuda
1.下载CUDA Toolkit https://developer.nvidia.com/cuda-toolkit-archive 2.按照命令下载,安装 sudo sh cuda_12.2.2_535.104.05_linux.run 3.环境变量 sudo vi /etc/profile 最后面添加 export PATH“/usr/local/cuda-12.2/bin: P A T H " e x p o r t L D L…...
unity li2cpp逆向原理是什么?
主要涉及将Unity游戏引擎中的C#代码转换为C代码,并进一步编译为各平台的原生(Native)代码的过程,以及逆向工程工具如何利用这一过程中的特定文件来还原和分析原始代码。以下是对Unity IL2CPP逆向原理的详细解释: 对惹…...
Python网络爬虫实践案例:爬取猫眼电影Top100
以下是一个Python网络爬虫的实践案例,该案例将演示如何使用Python爬取猫眼电影Top100的电影名称、主演和上映时间等信息,并将这些信息保存到TXT文件中。此案例使用了requests库来发送HTTP请求,使用re库进行正则表达式匹配,并包含详…...
卷积神经网络(CNN)中的权重(weights)和偏置项(bias)
在卷积神经网络(CNN)中,权重(weights)和偏置项(bias)是两个至关重要的参数,它们在网络的学习和推断过程中起着关键作用。 一、权重(Weights) 1. 定义…...
华为FusionCube 500-8.2.0SPC100 实施部署文档
环境: 产品:FusionCube 500版本:8.2.0.SPC100场景:虚拟化基础设施平台:FusionCompute两节点 MCNA * 2硬件部署(塔式交付场景)免交换组网(配置AR卡) 前置准备 组网规划 节…...
Android 网络请求(二)OKHttp网络通信
学习笔记 OkHttp 是一个非常强大且流行的 HTTP 客户端库,广泛用于 Android 开发中进行网络请求。与 HttpURLConnection 相比,OkHttp 提供了更简单、更高效的 API,特别是在处理复杂的 HTTP 请求时。 如何使用 OkHttp 进行网络请求 以下是使…...
npm上传自己封装的插件(vue+vite)
一、npm账号及发包删包等命令 若没有账号,可在npm官网:https://www.npmjs.com/login 进行注册。 在当前项目根目录下打开终端命令窗口,常见命令如下: 1、登录命令:npm login(不用每次都重新登录࿰…...
如何在Word文件中设置水印以及如何禁止修改水印
在日常办公和学习中,我们经常需要在Word文档中设置水印,以保护文件的版权或标明文件的机密性。水印可以是文字形式,也可以是图片形式,能够灵活地适应不同的需求。但仅仅设置水印是不够的,有时我们还需要确保水印不被随…...
.NET桌面应用架构Demo与实战|WPF+MVVM+EFCore+IOC+DI+Code First+AutoMapper
目录 .NET桌面应用架构Demo与实战|WPFMVVMEFCoreIOCDICode FirstAutoPapper技术栈简述项目地址:功能展示项目结构项目引用1. 新建模型2. Data层,依赖EF Core,实现数据库增删改查3. Bussiness层,实现具体的业务逻辑4. Service层&am…...
el-table根据指定字段合并行和列+根据屏幕高度实时设置el-table的高度
文章目录 html代码script代码arraySpanMethod.js代码 html代码 <template><div class"rightBar"><cl-table ref"tableData"border :span-method"arraySpanMethod" :data"tableData" :columns"columns":max-…...
Motrix Next v3.8.10 | 开源多线程下载管理器神器
Motrix Next v3.8.10是一款全新重构升级的开源多线程下载管理器,老牌原版 Motrix 早已停止更新,老旧架构存在诸多安全漏洞与性能缺陷。而 Motrix Next 基于 Tauri 2Vue3 全新重构开发,补齐了原版技术短板,软件全程纯净无任何广告加…...
Multisim仿真避坑指南:为什么你的74LS148电路LED灯不亮?从命名规则到电源接法的常见错误排查
Multisim仿真避坑指南:74LS148电路LED不亮的深度排查手册 当你在Multisim中搭建完一个看似完美的74LS148优先编码器电路,按下仿真按钮后却发现LED灯顽固地保持黑暗——这种挫败感每位电子工程师都深有体会。本文将从五个关键维度系统梳理那些容易被忽视却…...
QQ空间说说备份终极指南:GetQzonehistory完整教程
QQ空间说说备份终极指南:GetQzonehistory完整教程 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 你是否曾经想要永久保存QQ空间里那些珍贵的青春回忆?那些承载着…...
Supervisely完整指南:5步打造AI视觉标注神器
Supervisely完整指南:5步打造AI视觉标注神器 【免费下载链接】supervisely Supervisely SDK for Python - convenient way to automate, customize and extend Supervisely Platform for your computer vision task 项目地址: https://gitcode.com/gh_mirrors/su…...
终极指南:Visual C++运行库合集AIO - 一站式解决Windows程序依赖问题
终极指南:Visual C运行库合集AIO - 一站式解决Windows程序依赖问题 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 你是否曾经在运行某些软件或游戏时…...
如何用bsf创建第一个3D场景:从零开始的完整教程
如何用bsf创建第一个3D场景:从零开始的完整教程 【免费下载链接】B3DFramework Modern C library for the development of real-time graphical applications 项目地址: https://gitcode.com/gh_mirrors/bs/B3DFramework bsf(B3DFramework&#x…...
【飞机】基于matlab数据驱动的多传感器飞机健康监测系统【含Matlab源码 15551期】
💥💥💥💥💥💥💞💞💞💞💞💞💞💞欢迎来到海神之光博客之家💞💞💞Ὁ…...
新手必学——git日常提交手册
对于编程新手来说,Git 是必备的开发工具,也是日常写代码、保存代码、同步代码的核心技能。很多新手写代码翻车、代码丢失、版本混乱、多人协作冲突,本质都是不会正确使用 Git 提交代码。这篇手册专为新手打造,不讲复杂原理&#x…...
后端工程师知识库
后端工程师深度课程 中文知识库 一套面向中级到高级后端工程师的系统进阶课程,共 9 大专题、146 篇万字长文,每篇含底层原理、代码示例、生产实践、陷阱清单与练习题。 📅 内容基准:2026 年 5 月 —— HTTP/3 主流、TLS 1.3 pos…...
赛昉科技昉·星光单板计算机:RISC-V开源架构从IP到系统平台的跨越
1. 从获奖新闻到技术内核:赛昉科技与RISC-V的破局之路 最近在技术圈里,一条关于赛昉科技在“思维实验室论坛”上斩获“年度企业”和“年度产品”双奖的消息,引起了不少开发者和硬件爱好者的讨论。对于不熟悉RISC-V领域的朋友来说,…...
