当前位置: 首页 > 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; 从当前城市到下一个城市的路程时间。 当前城市的…...

HTTP 协议应用场景

一、HTTP 协议简介 HTTP&#xff08;Hypertext Transfer Protocol&#xff09;即超文本传输协议&#xff0c;是用于分布式、协作式和超媒体信息系统的应用层协议&#xff0c;是互联网数据通信的基础。它采用客户端 - 服务器&#xff08;Client-Server&#xff09;的通信模式&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是文本过滤器&#xff0c;其作用是在指定的文件中过滤出包含你指定字符串的内容&#xff0c;…...

python: generator model using sql server 2019

設計或生成好數據庫&#xff0c;可以生成自己設計好的框架項目 # encoding: utf-8 # 版权所有 &#xff1a;2024 ©涂聚文有限公司 # 许可信息查看 &#xff1a;言語成了邀功盡責的功臣&#xff0c;還需要行爲每日來值班嗎 # 描述&#xff1a; : 生成实体 # 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的安装 基于直接设备情况&#xff0c;选择合适的torch版本&#xff0c;有显卡的建议安装GPU版本&#xff0c;可以通过nvidia-smi命令来查看显卡驱动的版本&#xff0c;在官网中根据cuda版本&#xff0c;选择合适的版本号&#xff0c;下面是安装示例代码 GPU&#xff…...

golang 嵌入式armv7l压缩编译打包

编译 Go 应用程序 go build -ldflags"-s -w" -o myapp.exe . 使用 UPX 压缩可执行文件&#xff08;window下载并设置环境变量&#xff09; 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> ) 名称&#xff1a;连接函数——join。 功能&#xff1a;把<list2>中的单词对应地加到<list1>的单词后面。如果<list1>的单词个数要比<list2>的多&#xff0c; 那么&#xff0c;<list1>中的多出…...

集合卡尔曼滤波(Ensemble Kalman Filter),用于二维滤波(模拟平面上的目标跟踪),MATLAB代码

集合卡尔曼滤波&#xff08;Ensemble Kalman Filter&#xff09; 文章目录 引言理论基础卡尔曼滤波集合卡尔曼滤波初始化预测步骤更新步骤卡尔曼增益更新集合 MATLAB 实现运行结果3. 应用领域结论 引言 集合卡尔曼滤波&#xff08;Ensemble Kalman Filter, EnKF&#xff09;是…...

北京申请中级职称流程(2024年)

想找个完整详细点的申请流程资料真不容易&#xff0c;做个分享送给需要的人吧。 不清楚为什么说文章过度宣传&#xff0c;把链接和页面去掉了&#xff0c;网上自己找一下。 最好用windows自带的EDGE浏览器打开申请网站&#xff0c;只有在开始申请的时间内才可以进行网上申报&…...

ubuntu.24安装cuda

1.下载CUDA Toolkit https://developer.nvidia.com/cuda-toolkit-archive 2.按照命令下载&#xff0c;安装 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代码&#xff0c;并进一步编译为各平台的原生&#xff08;Native&#xff09;代码的过程&#xff0c;以及逆向工程工具如何利用这一过程中的特定文件来还原和分析原始代码。以下是对Unity IL2CPP逆向原理的详细解释&#xff1a; 对惹…...

Python网络爬虫实践案例:爬取猫眼电影Top100

以下是一个Python网络爬虫的实践案例&#xff0c;该案例将演示如何使用Python爬取猫眼电影Top100的电影名称、主演和上映时间等信息&#xff0c;并将这些信息保存到TXT文件中。此案例使用了requests库来发送HTTP请求&#xff0c;使用re库进行正则表达式匹配&#xff0c;并包含详…...

卷积神经网络(CNN)中的权重(weights)和偏置项(bias)

在卷积神经网络&#xff08;CNN&#xff09;中&#xff0c;权重&#xff08;weights&#xff09;和偏置项&#xff08;bias&#xff09;是两个至关重要的参数&#xff0c;它们在网络的学习和推断过程中起着关键作用。 一、权重&#xff08;Weights&#xff09; 1. 定义&#xf…...

华为FusionCube 500-8.2.0SPC100 实施部署文档

环境&#xff1a; 产品&#xff1a;FusionCube 500版本&#xff1a;8.2.0.SPC100场景&#xff1a;虚拟化基础设施平台&#xff1a;FusionCompute两节点 MCNA * 2硬件部署&#xff08;塔式交付场景&#xff09;免交换组网&#xff08;配置AR卡&#xff09; 前置准备 组网规划 节…...

Android 网络请求(二)OKHttp网络通信

学习笔记 OkHttp 是一个非常强大且流行的 HTTP 客户端库&#xff0c;广泛用于 Android 开发中进行网络请求。与 HttpURLConnection 相比&#xff0c;OkHttp 提供了更简单、更高效的 API&#xff0c;特别是在处理复杂的 HTTP 请求时。 如何使用 OkHttp 进行网络请求 以下是使…...

npm上传自己封装的插件(vue+vite)

一、npm账号及发包删包等命令 若没有账号&#xff0c;可在npm官网&#xff1a;https://www.npmjs.com/login 进行注册。 在当前项目根目录下打开终端命令窗口&#xff0c;常见命令如下&#xff1a; 1、登录命令&#xff1a;npm login&#xff08;不用每次都重新登录&#xff0…...

如何在Word文件中设置水印以及如何禁止修改水印

在日常办公和学习中&#xff0c;我们经常需要在Word文档中设置水印&#xff0c;以保护文件的版权或标明文件的机密性。水印可以是文字形式&#xff0c;也可以是图片形式&#xff0c;能够灵活地适应不同的需求。但仅仅设置水印是不够的&#xff0c;有时我们还需要确保水印不被随…...

.NET桌面应用架构Demo与实战|WPF+MVVM+EFCore+IOC+DI+Code First+AutoMapper

目录 .NET桌面应用架构Demo与实战|WPFMVVMEFCoreIOCDICode FirstAutoPapper技术栈简述项目地址&#xff1a;功能展示项目结构项目引用1. 新建模型2. Data层&#xff0c;依赖EF Core&#xff0c;实现数据库增删改查3. Bussiness层&#xff0c;实现具体的业务逻辑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-…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...