当前位置: 首页 > news >正文

洛谷 P8802 [蓝桥杯 2022 国 B] 出差

文章目录

  • [蓝桥杯 2022 国 B] 出差
    • 题目链接
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
  • 思路解析
  • CODE



[蓝桥杯 2022 国 B] 出差

题目链接

https://www.luogu.com.cn/problem/P8802

题目描述

A \mathrm{A} A 国有 N N N 个城市,编号为 1 … N 1 \ldots N 1N 小明是编号为 1 1 1 的城市中一家公司的员工,今天突然接到了上级通知需要去编号为 N N N 的城市出差。

由于疫情原因,很多直达的交通方式暂时关闭,小明无法乘坐飞机直接从城市 1 1 1 到达城市 N N N,需要通过其他城市进行陆路交通中转。小明通过交通信息网,查询到了 M M M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

同样由于疫情原因,小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络,小明也查询到了各个城市的隔离信息。(由于小明之前在城市 1 1 1,因此可以直接离开城市 1 1 1,不需要隔离)

由于上级要求,小明希望能够尽快赶到城市 N \mathrm{N} N, 因此他求助于你,希望你能帮他规划一条路线,能够在最短时间内到达城市 N N N

输入格式

1 1 1 行:两个正整数 N , M N, M N,M 表示 A 国的城市数量, M M M 表示末关闭的路线数量。

2 2 2 行: N N N 个正整数,第 i i i 个整数 C i C_{i} Ci 表示到达编号为 i \mathrm{i} i 的城市后需要隔离的时间。

3 … M + 2 3 \ldots M+2 3M+2 行: 每行 3 3 3 个正整数, u , v , c u, v, c u,v,c, 表示有一条城市 u u u 到城市 v v v 的双向路线仍然开通着,通过该路线的时间为 c c c

输出格式

1 1 1 行: 1 1 1 个正整数,表示小明从城市 1 1 1 出发到达城市 N N N 的最短时间。(到达城市 N N N,不需要计算城市 N N N 的隔离时间)

样例 #1

样例输入 #1

4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5

样例输出 #1

13

提示

【样例说明】

【评测用例规模与约定】

对于 100 % 100 \% 100% 的数据, 1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000 , 1 ≤ C i ≤ 200 , 1 ≤ u , v ≤ 1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq 1N1000,1M10000,1Ci200,1u,v N , 1 ≤ c ≤ 1000 N, 1 \leq c \leq 1000 N,1c1000

蓝桥杯 2022 国赛 B 组 E 题。



思路解析

求单源最短路问题,不过需要额外加上隔离天数的板子题。
最后别忘了减去城市 N N N 的隔离天数。


CODE

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f using namespace std;typedef pair<int, int> pii;const int N = 1010, M = 20010;
int h[N], e[M], ne[M], w[M], idx, c[N]; // 定义邻接表的数组,以及每个点的收费
int n, m; 		// 定义点数和边数
int dist[N]; 	// 定义到每个点的最短距离
bool st[N]; 	// 定义每个点是否在队列中的标记void add(int a, int b, int c){e[idx] = b; 	// 存储边的终点ne[idx] = h[a]; // 存储边的下一条边的编号w[idx] = c; 	// 存储边的权值h[a] = idx++; 	// 更新头结点的编号
}void spfa(){memset(dist, INF, sizeof dist); // 初始化距离为无穷大dist[1] = 0; 	// 起点到自己的距离为0queue<int> q; 	// 定义一个队列q.push(1); 		// 将起点入队st[1] = true; 	// 标记起点已经在队列中while(q.size()){ 	// 当队列不为空时循环int t = q.front(); // 取出队首元素q.pop(); 		// 将队首元素出队st[t] = false; 	// 标记该元素已经出队for(int i = h[t]; i != -1; i = ne[i]){ // 遍历该元素相邻的边int j = e[i]; // 获取边的终点// 如果可以用该边松弛终点的距离,即加上路线时间和隔离时间后比原来的距离小if(dist[j] > dist[t] + w[i] + c[j]){ dist[j] = dist[t] + w[i] + c[j]; // 更新终点的距离if(!st[j]){ 	// 如果终点不在队列中q.push(j); 	// 将终点入队st[j] = true; // 标记终点已经在队列中}}}}
}int main(){cin >> n >> m; 	// 输入城市数和路线数memset(h, -1, sizeof h); 	// 初始化邻接表头结点为-1for(int i = 1; i <= n; ++i)scanf("%d", &c[i]); 	// 输入每个城市的隔离时间while(m--){ int a, b, c;scanf("%d%d%d", &a, &b, &c); 	// 输入一条路线的两个端点和时间add(a, b, c), add(b, a, c); 	// 将该路线加入邻接表,注意是双向路线,所以要加两次}spfa(); // 调用spfa算法求最短路// 输出到达城市n的最短时间,注意要减去城市n的隔离时间,因为题目要求不计算城市n的隔离时间cout << dist[n] - c[n] << endl; 
}

相关文章:

洛谷 P8802 [蓝桥杯 2022 国 B] 出差

文章目录 [蓝桥杯 2022 国 B] 出差题目链接题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路解析CODE [蓝桥杯 2022 国 B] 出差 题目链接 https://www.luogu.com.cn/problem/P8802 题目描述 A \mathrm{A} A 国有 N N N 个城市&#xff0c;编号为 1 … N …...

fastadmin配置教程

第一. 打开小皮&#xff0c;创建一个网站 第二. 打开fastadmin官网&#xff0c;下载压缩包 下载好后是这个样子 打开网站的根目录&#xff0c;将这个压缩包压缩到你网站的根目录里 第三&#xff0c;小皮里面创建一个数据库 第四&#xff0c;然后打开网站&#xff0c;输入创…...

golang游戏服务器 - tgf系列课程01

TGF框架的特点和功能 课程介绍了TGF框架的特点和功能在第一节课程中我们并不会介绍框架的使用。我们希望在这节课程中,能让你了解到tgf是一个什么样的框架 概要 本节课程介绍了TGF框架的特点和功能。TGF是一个开箱即用的服务器框架, 适合中小型团队和独立开发者进行游戏开发。…...

react dom的diff理解及性能优化

diff的三大过程 当某个值变化时&#xff0c;他从根组件寻找 (key,state,props,context) 当父组件稳定时&#xff0c;react会跳过子组件的props的对比 只有当当前组件值改变时&#xff0c;从他开始&#xff0c;所有的子孙节点都会对比props props是全等比较&#xff0c;所以&am…...

【acwing】92. 递归实现指数型枚举

穿越隧道 递归枚举、位运算 方法① 从1到n&#xff0c;顺序访问每位数&#xff0c;是否选择&#xff0c;每位数有两种状态&#xff0c;选1或不选0. AC代码如下&#xff1a; #include <iostream> using namespace std;const int N 100; // bool st[N]; int n;void dfs(in…...

【面试】Java最新面试题资深开发-分布式系统中的CAP理论

问题六&#xff1a;分布式系统中的CAP理论 分布式系统的设计涉及到CAP理论&#xff0c;即一致性&#xff08;Consistency&#xff09;、可用性&#xff08;Availability&#xff09;、分区容忍性&#xff08;Partition Tolerance&#xff09;。请解释一下CAP理论是什么&#x…...

Windows下使用CMD修改本地IP

在网络适配器界面查看当前网线连接的哪个网口&#xff0c;我当前连的是 以太网 这个名字的&#xff1a; 在windows下使用管理员权限打开CMD命令工具&#xff0c;输入如下命令(如我想本地ip改成192.168.2.4)&#xff1a; netsh interface ip set address "以太网" st…...

20231211-DISM++安装win10-22h2-oct

20231211-DISM安装win10-22h2-oct 一、软件环境 zh-cn_windows_10_consumer_editions_version_22h2_updated_oct_2023_x64_dvd_eb811ccc.isowepe x64 v2.3标签&#xff1a;win10 22h2 wepe dism分栏&#xff1a;WINDOWS 二、硬件环境 8G或以上的有PE功能的启动U盘一个台式机…...

前端知识笔记(五)———前端密钥怎么存储,才最安全?

前端密钥存储安全是非常重要的&#xff0c;具体原因如下&#xff1a; 保护敏感数据&#xff1a;密钥用于保护敏感数据的安全性。如果密钥泄露&#xff0c;攻击者可能能够访问和篡改敏感数据&#xff0c;导致数据泄露、数据被篡改或系统被入侵。 防止恶意使用&#xff1a;在前端…...

【智能家居】智能家居项目

智能家居项目目录 项目目录结构 完整而典型的项目目录结构 CMake模板 CMake编译运行 README.md 项目说明文档 智能家居项目目录 【智能家居】面向对象编程OOP和设计模式(工厂模式) 【智能家居】一、工厂模式实现继电器灯控制 【智能家居】二、添加火灾检测模块&#xff08;…...

在AWS Lambda上部署标准FFmpeg工具——Docker方案

大纲 1 确定Lambda运行时环境1.1 Lambda系统、镜像、内核版本1.2 运行时1.2.1 Python1.2.2 Java 2 启动EC23 编写调用FFmpeg的代码4 生成docker镜像4.1 安装和启动Docker服务4.2 编写Dockerfile脚本4.3 生成镜像 5 推送镜像5.1 创建存储库5.2 给EC2赋予角色5.2.1 创建策略5.2.2…...

C#网络应用程序(Web页面浏览器、局域网聊天程序)

目录 一、创建Web页面浏览器 1.示例源码 2.生成效果 二、局域网聊天程序 1.类 2.服务器端 3.客户端 一、创建Web页面浏览器 TextBox 控件用来输入要浏览的网页地址&#xff0c;Button控件用来执行浏览网页操作&#xff0c; WebBrowser控件用来显示要浏览的网页。这个控…...

MacOS 14挂载NTFS 硬盘的最佳方式(免费)

categories: [Tips] tags: MacOS 写在前面 众所周知, MacOS 上面插入 NTFS磁盘格式的话, 磁盘可以向 Mac 写入数据, 但是 Mac 上的数据不能写入磁盘(这是因为 MacOS 的内核扩展禁用了 NTFS 这个格式, 可能是出于安全性或其他原因) 之前一直是使用某 pojie 的 NTFS 工具的, 虽然…...

SpringAOP专栏二《原理篇》

上一篇SpringAOP专栏一《使用教程篇》-CSDN博客介绍了SpringAop如何使用&#xff0c;这一篇文章就会介绍Spring AOP 的底层实现原理&#xff0c;并通过源代码解析来详细阐述其实现过程。 前言 Spring AOP 的实现原理是基于动态代理和字节码操作的。不了解动态代理和字节码操作…...

冒泡排序(函数)

冒泡排序&#xff0c;将一个列表中的两个元素进行比较&#xff0c;并将最小的元素交换到顶部。两个元素中较小的会冒到顶部&#xff0c;而较大的会沉到底部&#xff0c;该过程将被重复执行&#xff0c;直到所有元素都被排序。 输入格式: 输入在第1行中给出N&#xff08;1<N…...

Vue3中的defineModel

目录 一、vue3的defineModel介绍 二、defineModel使用 &#xff08;1&#xff09;在vite.config.js中开启 &#xff08;2&#xff09;子组件 &#xff08;3&#xff09;父组件 一、vue3的defineModel介绍 为什么要使用到defineModel呢&#xff1f;这里有这样一种场景&…...

动态内存管理(C语言)

前言 在学习数据结构时&#xff0c;掌握指针、结构体和动态内存管理是非常关键的&#xff0c;它们就像是搭建程序框架和操作内存的工具箱&#xff0c;需要熟练掌握才能更加游刃有余地进行编程。 指针和结构体我们已经在之前详细的讲过了&#xff0c;今天我将带大家学习动态内存…...

区块链实验室(32) - 下载arm64的Prysm

Prysm是Ethereum的共识层。 1. 下载prysm.sh curl https://raw.githubusercontent.com/prysmaticlabs/prysm/master/prysm.sh --output prysm.sh && chmod x prysm.sh2. 下载x86版prysm共识客户端 ./prysm.sh beacon-chain --download-only3.下载arm64版prysm共识客…...

flutter学习-day3-dart基础

&#x1f4da; 目录 变量声明操作符数据类型控制流错误处理和捕获函数mixin异步 FutureStream 本文学习和引用自《Flutter实战第二版》&#xff1a;作者&#xff1a;杜文 1. 变量声明 var 类似于 JavaScript 中的var&#xff0c;它可以接收任何类型的变量&#xff0c;但最大…...

gitblit自建git仓库

在Ubuntu服务器 安装 java sudo apt-get update sudo apt-get install openjdk-8-jdk # 或者其它你喜欢的版本//sudo snap install gitblit 验证&#xff1a; java -version下载 gitblit https://github.com/gitblit-org/gitblit/releases解压/usr/local tar -zxvf gitb…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...