当前位置: 首页 > 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-…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...