【洛谷 P8802】[蓝桥杯 2022 国 B] 出差 题解(带权无向图+单源最短路+Dijkstra算法+链式前向星+最小堆)

[蓝桥杯 2022 国 B] 出差

题目描述

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 和开放的路线数量 m。然后读取每个城市的隔离时间,存储在数组 c 中。接着读取 m 条边的信息,每条边包含起始城市 u,目标城市 v,以及通过该路线需要的时间 w。对于每条边,都将其添加到链式前向星中,同时将该城市的隔离时间加到边的权重上。这样做的目的是在计算从城市 u 到城市 v 的时间时,同时考虑了在城市 v 的隔离时间。

通过 Dijkstra 算法来找到从城市 1 到城市 n 的最短路径。使用 vis.reset() 初始化所有节点为未访问状态。然后,对于每个节点,如果节点是源点(城市 1),则其到自己的最短距离 dist[i] 为 0,并将其加入优先队列 hmin 中。否则,将其最短距离设置为无穷大,并将其前驱节点 prior[i] 设置为 -1,表示还没有找到到达它的最短路径。

然后进入主循环,当优先队列不为空时,取出队列顶部的节点 t,其中 t.v 是节点编号,t.d 是从源点到该节点的当前最短距离。如果该节点已经被访问过,则跳过。否则,将其标记为已访问。然后,遍历从节点 u 出发的所有边,如果通过当前边到达节点 v 的距离 du + edge[i].w 小于 v 的当前最短距离 dist[v],则更新 dist[v],并将 v 加入优先队列。

这个过程会持续,直到优先队列为空,或者找到目标节点 n。注意,dist[v] 中的值是从源点到达 v 并在 v 进行隔离的总时间,所以在最后的结果中需要减去城市 n 的隔离时间。

注意

  1. 到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市,将终点城市的隔离时间加到边的权重上即可。
  2. 到达城市 n 后不需要隔离,所以在最后的结果中需要减去城市 n 的隔离时间。

AC代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

struct Edge {
	int w, to, next;
} edge[N];
int head[N];
int cnt = 0;

struct Node {
	int v, d;
	bool operator<(const Node &b) const { return d > b.d; }
};

int n, m;
int c[N];

// 最短路径长度
int dist[N];
// 前驱节点
int prior[N];
bitset<N> vis;
priority_queue<Node> hmin;

void add(int u, int v, int w) {
	edge[cnt] = {w, v, head[u]};
	head[u] = cnt++;
}

void dijkstra() {
	vis.reset();
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			dist[i] = 0;
			hmin.push({i, 0});
		} else {
			dist[i] = INF;
			prior[i] = -1;
		}
	}
	while (hmin.size()) {
		auto t = hmin.top();
		hmin.pop();
		int u = t.v;
		int du = t.d;
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		for (int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dist[v] > (du + edge[i].w)) {
				dist[v] = du + edge[i].w;
				prior[v] = u;
				hmin.push({v, dist[v]});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(head, -1, sizeof(head));

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		// 到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市
		add(u, v, w + c[v]);
		add(v, u, w + c[u]);
	}
	dijkstra();
	// 到达n城后不需要隔离
	cout << dist[n] - c[n] << "\n";
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【GEE实践应用】统计遥感数据像元的观测值数量以及良好观测值数量

下面我们以贵州省毕节市2016年8月1号至2018年7月31号两年间像元的观测值数量以及良好的观测值数量为例&#xff0c;统计结果以图像形式进行输出&#xff0c;如图1所示&#xff1a; // 1. 定义研究区域 var studyArea table;// 获取 Landsat 和 Sentinel-2 数据集 var landsat…

第九届少儿模特明星盛典 全球赛首席体验官『韩嘉滢』精彩回顾

2024年1月30日-2月1日&#xff0c;魔都上海迎来了龙年第一场“少儿形体行业美育春晚”&#xff01;由IPA模特委员会主办的第九届少儿模特明星盛典全球总决赛圆满收官&#xff01;近2000名少儿模特选手从五湖四海而来&#xff0c;决战寒假这场高水准&#xff0c;高人气&#xff…

前端上传照片压缩 (适合 vue vant组件的)

为什么要这样做&#xff1f; &#xff08;减小服务器压力 提升用户体验上传照片和加载照片会变快&#xff09; 最近有一个需求&#xff0c;通过手机拍照后上传图片到服务器&#xff0c;大家应该都知道&#xff0c;现在的手机像素实在是太高了&#xff0c;随便拍一张都是10M以上…

物联网的核心价值是什么?——青创智通

工业物联网解决方案-工业IOT-青创智通 物联网&#xff0c;这个词汇在当今的科技领域已经变得耳熟能详。但当我们深入探索物联网的核心价值时&#xff0c;我们会发现它远不止是一个简单的技术概念&#xff0c;而是一种能够彻底改变我们生活方式和工作方式的革命性力量。 物联网…

Django之rest_framework(三)

一、GenericAPIView的使用 rest_framework.generics.GenericAPIView 继承自APIVIew,主要增加了操作序列化器和数据库查询的方法,作用是为下面Mixin扩展类的执行提供方法支持。通常在使用时,可搭配一个或多个Mixin扩展类 1.1、属性 serializer_class 指明视图使用的序列化器…

JVM之JVM栈的详细解析

Java 栈 Java 虚拟机栈&#xff1a;Java Virtual Machine Stacks&#xff0c;每个线程运行时所需要的内存 每个方法被执行时&#xff0c;都会在虚拟机栈中创建一个栈帧 stack frame&#xff08;一个方法一个栈帧&#xff09; Java 虚拟机规范允许 Java 栈的大小是动态的或者是…

npm配置阿里镜像库

1、配置阿里云镜像源 #查看当前使用的镜像地址命令 npm config get registry#设置阿里镜像源 npm config set registry http://registry.npmmirror.com 这里要注意下&#xff0c;之前的镜像源地址 https://registry.npm.taobao.org/ 已经不能用了&#xff0c;这里要更改为新…

Grok-1.5 Vision 预览 将数字世界与物理世界连接起来,首款多模态模型

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

android 创建module

文章目的&#xff1a; 快速创建module并使用 创建步骤&#xff1a; 1 创建module 2 修改module下的build.gradle文件 3 修改清单文件中MainActivity属性&#xff0c;否则APP会因为有多个启动界面而崩溃 4 在主项目build.gradle引用该object Module 至此&#xff0c;可在APP中…

golang 迷宫回溯算法(递归)

// Author sunwenbo // 2024/4/14 20:13 package mainimport "fmt"// 编程一个函数&#xff0c;完成老鼠找出路 // myMap *[8][7]int 地图&#xff0c;保证是同一个地图&#xff0c;因此是引用类型 // i,j表示对地图的哪个点进行测试 func SetWay(myMap *[8][7]int, …

【ARM 裸机】汇编 led 驱动之烧写 bin 文件

1、烧写概念 bin 文件烧写到哪里呢&#xff1f;使用 STM32 的时候烧写到内部 FLASH&#xff0c;6ULL 没有内部 FLASH&#xff0c;是不是就不能烧写呢&#xff1f;不&#xff0c;6ULL 支持 SD卡、EMMC、NAND FLASH、NOR FLASH 等方式启动&#xff0c;在裸机学习的工程中&#x…

参会记录|全国多媒体取证暨第三届多媒体智能安全学术研讨会(MAS‘2024)

前言&#xff1a;2024年4月13日上午&#xff0c;我与实验室的诸位伙伴共聚江西南昌的玉泉岛大酒店&#xff0c;参加了为期一天半的全国多媒体取证暨第三届多媒体智能安全学术研讨会&#xff08;MAS’2024&#xff09;。本届学术研讨会由江西省计算机学会、江西省数字经济学会主…

【学习笔记十七】波次管理、自动波次和WOCR介绍及配置

一、手工维护波次 波次是控制仓库活动(如拣配)的仓库请求项目(通常是出库交货订单项目)的分组。这些分组随后在后续流程中一起处理,例如,将分配到波次的所有仓库请求项目传输到仓库任务创建。 注意:仓库请求是出库交货订单、过账更改、库存转储(用于仓库中的内部移动)或入库…

最短网络kruskal算法

题目描述 农民约翰被选为他们镇的镇长&#xff01;他其中一个竞选承诺就是在镇上建立起互联网&#xff0c;并连接到所有的农场。当然&#xff0c;他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路&#xff0c;他想把这条线路共享给其他农场。为了用最小的消费&…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之十一 简单给视频添加水印图片效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之十一 简单给视频添加水印图片效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之十一 简单给视频添加水印图片效果 一、简单介绍 二、简单给视频添加水印图片效果实现…

【保姆级讲解Element UI】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

负载均衡器如何工作,为什么如此重要?

现代应用程序和网站处理大量流量。负载均衡器是保证大型系统平稳运行的主要工具之一。 负载平衡器负责跨多个服务器路由客户端请求以分配负载并防止出现瓶颈。 这有助于最大限度地提高吞吐量、减少响应时间并优化资源使用。 负载均衡器的运行情况&#xff1a; (1).客户端请…

面试算法-176-验证二叉搜索树

题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1&#x…

C++内存管理与模版(用法详解)

C/C中程序内存区域划分 内核空间&#xff08;用户代码不能读写&#xff09;栈&#xff08;函数中存放的变量&#xff09;内存映射段堆&#xff08;重点&#xff09;数据段&#xff08;静态区&#xff09;全局变量 / 静态变量代码段&#xff08;常量区&#xff09; 试分析下列…

大模型用到的位置编码汇总(面试)

不同于RNN、CNN等模型&#xff0c;对于Transformer模型来说&#xff0c;位置编码的加入是必不可少的&#xff0c;因为纯粹的Attention模块是无法捕捉输入顺序的&#xff0c;即无法区分不同位置的Token。为此我们大体有两个选择&#xff1a;想办法将位置信息融入到输入中&#x…