蓝桥杯每日真题 - 第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]

难度分析

⭐️⭐️⭐️⭐️⭐️难难难难难急急急急急急急

总结

本代码解决了一个加权图中的特殊最短路径问题,考虑到离开时间的影响。
它适用于小型的城市网络,提供了可靠的解法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/475371.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

每日论文23-24ESSERC 6.4-16.1Ghz混合并联-串联谐振器

《A 6.4-to-16.1GHz Hybrid Parallel-Series Resonator Mode-Switching Oscillator with 206.6dBc/Hz FoMT at 1MHz Offset in 40nm CMOS》 24ESSERC 首先这篇文章有个地方我其实没太明白&#xff0c;它在title和行文的时候都写的是“ hybrid parallel-series resonator mode-…

<QNAP 453D QTS-5.x> 日志记录:在 Docker 中运行的 Flask 应用安装 自签名 SSL 证书 解决 Chrome 等浏览器证书安全

原因&#xff1a;Chrome 不信任 ssc 证书 使启用了 HTTPS&#xff0c;即使有使用 自签名证书 (self-signed certificate 非由可信的证书颁发机构 【CA&#xff0c;Certificate Authority】签发的&#xff09;。浏览器 Chrome 默认不信任自签名证书&#xff0c;也会报 NET::ERR_…

【再谈设计模式】适配器模式 ~接口兼容的桥梁

一、引言 在软件开发的复杂世界里&#xff0c;不同的组件、类或者系统往往有着各自独立的设计和接口定义。当需要将这些原本不兼容的部分整合在一起协同工作时&#xff0c;就像尝试将方形的榫头插入圆形的卯眼一样困难。适配器设计模式就如同一位神奇的工匠&#xff0c;能够巧妙…

无人机的激光雷达避障系统阐述!

一、材料 激光二极管基底材料&#xff1a;激光二极管是激光雷达的核心组件之一&#xff0c;其基底材料通常采用硅或砷化镓。硅材料成本低、易于加工&#xff0c;但发光效率相对较低&#xff1b;而砷化镓材料发光效率高&#xff0c;但成本较高。 光学镜片材料&#xff1a;激光…

一篇快速上手 Axios,一个基于 Promise 的网络请求库(涉及原理实现)

Axios 1. 介绍1.1 什么是 Axios&#xff1f;1.2 axios 和 ajax 的区别 2. 安装使用3. Axios 基本使用3.1 Axios 发送请求3.2 其他方式发送请求3.3 响应结构3.4 Request Config3.5 默认配置3.6 创建实例对象发送请求 3.7 拦截器3.8 取消请求 4. 模拟 Axios4.1 axios 对象创建过程…

Three.js 相机控制器Controls

在 3D 场景中&#xff0c;摄像机的控制尤为重要&#xff0c;因为它决定了用户如何观察和与场景互动。Three.js 提供了多种相机控制器&#xff0c;最常用的有 OrbitControls、TrackballControls、FlyControls 和 FirstPersonControls。OrbitControls 适合用于查看和检查 3D 模型…

【新人系列】Python 入门(十一):控制结构

✍ 个人博客&#xff1a;https://blog.csdn.net/Newin2020?typeblog &#x1f4dd; 专栏地址&#xff1a;https://blog.csdn.net/newin2020/category_12801353.html &#x1f4e3; 专栏定位&#xff1a;为 0 基础刚入门 Python 的小伙伴提供详细的讲解&#xff0c;也欢迎大佬们…

SELinux

一、简介 SELinux : 安全强化的Linux&#xff1b;在开启后,会对进程本身部署安全上下文&#xff1b;会对文件部署安全上下文&#xff1b;对法务使用端口进行限制&#xff1b;对程序本身的不安全功能做限制 二、工作原理 1、工作方式 通过MAC的方式来控制管理进程&#xff0…

C++小白实习日记——Day 5 gitee怎么删文件,测试文件怎么写循环

昨晚一直内耗&#xff0c;一个程序写了三天写不出来&#xff0c;主要是耗时太多了&#xff0c;老板一直不满意。想在VScode上跑一下&#xff0c;昨晚一直报错。今天来公司重新搞了一下&#xff0c; 主要工作有&#xff1a; 1&#xff0c;读取当前时间用tscns 2&#xff0c;输…

Apache Paimon】-- 6 -- 清理过期数据

目录 1、简要介绍 2、操作方式和步骤 2.1、调整快照文件过期时间 2.2、设置分区过期时间 2.2.1、举例1 2.2.2、举例2 2.3、清理废弃文件 3、参考 1、简要介绍 清理 paimon &#xff08;表&#xff09;过期数据可以释放存储空间&#xff0c;优化资源利用并提升系统运行效…

阿里云IIS虚拟主机部署ssl证书

宝塔配置SSL证书用起来是很方便的&#xff0c;只需要在站点里就可以配置好&#xff0c;但是云虚拟主机在管理的时候是没有这个权限的&#xff0c;只提供了简单的域名管理等信息。 此处记录下阿里云&#xff08;原万网&#xff09;的IIS虚拟主机如何配置部署SSL证书。 进入虚拟…

BOM的详细讲解

BOM概述 BOM简介 BOM&#xff08;browser Object&#xff09;即浏览器对象模型&#xff0c;它提供了独立于内容而与浏览器窗口进行交互的对象&#xff0c;其核心对象是window。 BOM由一系列的对象构成&#xff0c;并且每个对象都提供了很多方法与属性 BOM缺乏标准&#xff…

湘潭大学软件工程算法设计与分析考试复习笔记(四)

回顾 湘潭大学软件工程算法设计与分析考试复习笔记&#xff08;一&#xff09;湘潭大学软件工程算法设计与分析考试复习笔记&#xff08;二&#xff09;湘潭大学软件工程算法设计与分析考试复习笔记&#xff08;三&#xff09; 前言 现在是晚上十一点&#xff0c;我平时是十…

STM32单片机ADC数模转换器

由于最近忘记了&#xff0c;自用。 转换模式 单次转换&#xff0c;非扫描模式 在非扫描模式下&#xff0c;列表中就只有序列1的位置有效&#xff0c;此时可以在序列1的位置指定我们想要转换的通道&#xff0c;然后ADC就会对这个通道进行模数转换。等待一段时间&#xff0c;转…

android 使用MediaPlayer实现音乐播放--获取音乐数据

前面已经添加了权限&#xff0c;有权限后可以去数据库读取音乐文件&#xff0c;一般可以获取全部音乐、专辑、歌手、流派等。 1. 获取全部音乐数据 class MusicHelper {companion object {SuppressLint("Range")fun getMusic(context: Context): MutableList<Mu…

Spring Boot中使用AOP和反射机制设计一个的幂等注解(两种持久化模式),简单易懂教程

该帖子介绍如何设计利用AOP设计幂等注解&#xff0c;且可设置两种持久化模式 1、普通模式&#xff1a;基于redis的幂等注解&#xff0c;持久化程度较低 2、增强模式&#xff1a;基于数据库&#xff08;MySQL&#xff09;的幂等注解&#xff0c;持久化程度高 如果只需要具有re…

VSCode+ESP-IDF开发ESP32-S3-DevKitC-1(1)开发环境搭建

VSCodeESP-IDF开发ESP32-S3-DevKitC-1&#xff08;1&#xff09;开发环境搭建 1.开发环境搭建&#xff08;安装ESP-IDF&#xff09;2.开发环境搭建&#xff08;安装VS Code&#xff09;3.开发环境搭建&#xff08;VSCode中安装ESP-IDF插件及配置&#xff09; 1.开发环境搭建&am…

论文分享 | FuzzLLM:一种用于发现大语言模型中越狱漏洞的通用模糊测试框架

大语言模型是当前人工智能领域的前沿研究方向&#xff0c;在安全性方面大语言模型存在一些挑战和问题。分享一篇发表于2024年ICASSP会议的论文FuzzLLM&#xff0c;它设计了一种模糊测试框架&#xff0c;利用模型的能力去测试模型对越狱攻击的防护水平。 论文摘要 大语言模型中…

opencv(c++)----图像的读取以及显示

opencv(c)----图像的读取以及显示 imread: 作用&#xff1a;读取图像文件并将其加载到 Mat 对象中。参数&#xff1a; 第一个参数是文件路径&#xff0c;可以是相对路径或绝对路径。第二个参数是读取标志&#xff0c;比如 IMREAD_COLOR 表示以彩色模式读取图像。 返回值&#x…