蓝桥杯每日真题 - 第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-…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...