蓝桥杯每日真题 - 第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-…...
告别检测卡点,okbiye 智能双优化破解毕业论文查重与 AI 识别难题
okbiye-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/AI PPT降重复率 - Okbiye智能写作https://www.okbiye.com/reduceAIGC 一、引言:论文定稿阶段两大检测难题普遍困扰学子 论文撰写收尾阶段,绝大多数毕业生都会直面两道审核关卡&#x…...
今天农巡车项目的摄像头云台问题及解决
今天在农巡车双舵机云台项目开发过程中,主要遇到了舵机不转、舵机只动一下就停止、运动过程中抖动严重、实际转动角度不足、扫描逻辑加入后上下舵机失效、左右舵机最后一次不转、程序下载后长时间无响应等问题。首先,在PWM输出阶段发现PB6和PB7的TIM4通道…...
【期刊征稿 | 录用后最快当月见刊,刊后1个月检索,且检索稳定】第九届艺术、教育与管理国际学术会议(ICAEM 2026) - 第二期
录用后最快当月见刊,刊后1个月检索,且检索稳定 | 含ISSN号,DOI,封面目录 第九届艺术、教育与管理国际学术会议(ICAEM 2026) - 第二期 2026 9th International Conference on Arts, Education and Management 2026年…...
手语识别实战:CNN-LSTM混合架构与轻量化部署指南
1. 项目概述:手语识别不是“翻译”,而是构建一座可触摸的沟通桥梁手语识别这件事,我从2019年第一次在残联康复中心做志愿者时就盯上了。当时一位老师傅用双手比划“苹果”“医院”“谢谢”,而旁边的年轻人盯着手机里刚装的某款APP…...
【Go i18n】TOML语言包
一、VS Code 必备的 TOML 插件1. Even Better TOML(核心高亮与语法检查 👑)搜索关键字:Even Better TOML为什么要装:它是目前全网公认第一的 TOML 插件。装上它之后,你的 .toml 文件不仅会变得色彩斑斓&…...
物流物联网降本增效:LoRa、NB-IoT等低功耗无线技术选型与实战
1. 项目概述:当“省电”成为物流降本增效的隐形王牌最近和几个做仓储和车队管理的朋友聊天,大家不约而同都在吐槽同一个问题:设备电费和管理成本。一个大型仓库里,成千上万个传感器、电子标签、手持终端,光是电池更换和…...
告别应用层延时!在迅为RK3568开发板上,将RS485收发切换彻底交给Linux内核驱动
告别应用层延时!在迅为RK3568开发板上将RS485收发切换彻底交给Linux内核驱动 工业自动化领域对通信实时性的要求近乎苛刻,当RS485总线上挂载的多个设备响应时间参差不齐时,应用层手动控制的收发切换就像用机械表校准原子钟——看似可行实则漏…...
2026年最新实测15款降AIGC平台红黑榜!
2026 年的毕业季注定不平凡。教育部最新发布的《学术诚信管理规范》明确指出,本科毕业论文 AIGC 率不得超过 35%,而重点高校如清华、北大等已将标准压至 25% 以内,硕士及以上学位论文更是严格控制在 18% 以下。与此同时,各大检测平…...
Waymo自动驾驶出租车频入洪水区,亚特兰大服务暂停!
TechCrunch导航栏TechCrunch有桌面端和移动端标志。网站有最新资讯、初创公司、风险投资、苹果、安全、人工智能、应用程序等分类,还有活动、播客、时事通讯等内容,具备搜索和巨型菜单切换功能。主题涉及最新资讯、人工智能、亚马逊等众多方面࿰…...
长期使用Taotoken后对账单清晰度与成本预测的体会
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 长期使用Taotoken后对账单清晰度与成本预测的体会 效果展示类,分享作为长期用户,如何依赖Taotoken提供的详…...
