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

AcWing算法提高课-3.1.1热浪

宣传一下算法提高课整理 <—

CSDN个人主页:更好的阅读体验 <—

csdn

题目传送门点这里

题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!!

他们的德克萨斯长角牛吃起来不错,可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇,为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用(包括油费,过路费等等)。

给定一个地图,包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs,终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

输入格式

第一行: 444 个由空格隔开的整数: T,C,Ts,TeT,C,T_s,T_eT,C,Ts,Te;

222 到第 C+1C+1C+1 行: 第 i+1i+1i+1 行描述第 iii 条道路,包含 333 个由空格隔开的整数: Rs,Re,CiR_s,R_e,C_iRs,Re,Ci

输出格式

一个单独的整数表示从 TsT_sTsTeT_eTe 的最小总费用。

数据保证至少存在一条道路。

数据范围

1≤T≤2500,1≤T≤2500,1T2500,
1≤C≤6200,1≤C≤6200,1C6200,
1≤Ts,Te,Rs,Re≤T,1≤T_s,T_e,R_s,R_e≤T,1Ts,Te,Rs,ReT,
1≤Ci≤10001≤C_i≤10001Ci1000

样例输入

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

样例输出

7

思路

我们先抽象出图:
题目的大致意思是,给定一个无向图并给定起点和终点,求其最短路径。

这就基本上是一道模板题了,作者在这里是用朴素Dijkstra算法写的。当然,有些同学为了节省时间,可能会用SPFA。但,这是个正权图,如果出题人非常敬业 (邪恶) 的话,就会把SPFA卡掉。

所以在OI赛制下,正权图的最短路尽量还是用Dijkstra,除非时间限制真的不够用。

因为本题的点数和边数都不是很大,所以原则上,无论用邻接表或者邻接矩阵都是可以存下的。

算法时间复杂度

假定这里n表示点数,m表示边数,则:

朴素Dijkstra算法的时间复杂度是O(n2)O(n^2)O(n2)
SPFA算法的时间复杂度一般是O(m)O(m)O(m),最坏情况下是O(nm)O(nm)O(nm)
堆优化Dijkstra的时间复杂度是O(mlog⁡n)O(m \log n)O(mlogn)

AC Code

C++C++C++

#include <iostream>
#include <cstring>using namespace std;const int N = 2520;int n, m, st, ed;
int g[N][N]; // 邻接矩阵存图
int dist[N]; // 存最短距离
bool f[N]; // 找过的点的集合int dijkstra(int st, int ed) // Dijkstra算法
{memset(dist, 0x3f, sizeof(dist)); // 初始化dist数组dist[st] = 0; // 起点距离设置为0for (int i = 1; i <= n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!f[j] && (t == -1 || dist[j] < dist[t]))t = j; // 找到当前与源点距离最短的那个点f[t] = 1; // 将该点标记上,表示这个点已经找过了for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]); // 用这个点更新源点与其他点的最短距离}return dist[ed]; // 返回st->ed的最短距离
}int main()
{memset(g, 0x3f, sizeof(g)); // 初始化邻接矩阵int a, b, c;scanf("%d%d", &n, &m);scanf("%d%d", &st, &ed);while (m -- ){scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);g[b][a] = min(g[b][a], c); // 因为可能有重边,所以需要取最小值}int res = dijkstra(st, ed);printf("%d\n", res); // 数据保证有解,故不需要判断return 0;
}

a

最后,如果觉得对您有帮助的话,点个赞再走吧!

相关文章:

AcWing算法提高课-3.1.1热浪

宣传一下算法提高课整理 <— CSDN个人主页&#xff1a;更好的阅读体验 <— 题目传送门点这里 题目描述 德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪&#xff01;&#xff01;&#xff01; 他们的德克萨斯长角牛吃起来不错&#xff0c;可是它们并不是很擅长生产富…...

华为OD机试题【最差产品奖】用 C++ 编码,速通 (2023.Q1)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明最差产…...

NFT市场大战:Blur市场地位可持续吗?

在战胜无数虚张声势的挑战者之后&#xff0c;OpenSea终于迎来了一个实力雄厚的竞争对手&#xff0c;已威胁到它的市场主导地位。opensea是什么&#xff1f;参考《NFT&#xff0c;区块链的产物之一&#xff0c;了解NFT交易平台Opensea》 继成功的空投之后&#xff0c;Blur并没有…...

初识CSS

1.CSS语法形式CSS基本语法规则就是:选择器若干属性声明由选择器选择一个元素,其中的属性声明就作用于该元素.比如:<body><p>这是一个段落</p><!-- style可以放在代码的任意地方 --><style>p{/* 将字体颜色设置为红色 */color: red;}</style&g…...

kubernetes(k8s)知识总结(第3期)

1. PV 与 PVC PV 是持久卷&#xff08;Persistent Volume&#xff09;的首字母缩写。通常情况下&#xff0c;可以事先在 k8s 集群创建 PV 对象&#xff1a; apiVersion: v1 kind: PersistentVolume metadata:name: nfs spec:storageClassName: manualcapacity:storage: 1Giac…...

浅谈跨境电商运行模式

近些年&#xff0c;由于疫情的原因和人们的消费习惯的改变&#xff0c;线下销售越来越不占优势&#xff0c;电商行业由于这几年的飞速发展&#xff0c;成功地吸引到我国的民众&#xff0c;拼多多、淘宝、京东、天猫等各种各样的国内电商平台涌现&#xff0c;依靠着产品质量好、…...

Memcached

什么是MemcachedMemcached 是一个开源免费的高性能的分布式内存对象缓存系统、就是一个软件Memcached的作用缓存数据提高动态网站的速度Memcached的安装//方法一yum installmemcached//方法二1.安装libevent (memcached依赖包)tar -zvxflibevent-release-1.4.15-stable.tar.gzc…...

Unity UGUI 拖拽组件

效果展示 使用方式 拖到图片上即可用 父节点会约束它的活动范围哦~ 父节点会约束它的活动范围哦~ 父节点会约束它的活动范围哦~ 源码 using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.EventSystems;/// <summary> /…...

面试总结——react生命周期

react生命周期总结 生命周期主要分为以下几个阶段&#xff1a; Mounting:创建虚拟DOM&#xff0c;渲染UI(初始化)Updating&#xff1a;更新虚拟DOM&#xff0c;重新渲染UI&#xff1b;(更新)UnMounting&#xff1a;删除虚拟DOM&#xff0c;移除UI&#xff1b;(销毁) 生命周期…...

初探推荐系统-01

文章目录一、什么是推荐系统是什么为什么长尾理论怎么做二、相似度算法杰卡德相似系数余弦相似度三、基于内容的推荐算法如何获取到用户喜欢的物品如何确定物品的特征四、推荐算法实验方法评测指标推荐效果实验方法1、离线实验2、用户调查3、在线实验评测指标1、预测准确度评分…...

html实现浪漫的爱情日记(附源码)

文章目录1.设计来源1.1 主界面1.2 遇见1.3 相熟1.4 相知1.5 相念2.效果和源码2.1 动态效果2.2 源代码2.3 代码结构源码下载更多爱情表白源码作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/129264757 html实现浪漫的爱情…...

detectron2容器环境安装问题(1)

1为避免后面出现需求python版本低于3.7的情况ERROR: Package detectron2 requires a different Python: 3.6.9 not in >3.7可以第一步就使用 nvidia/cuda:11.1.1-cudnn8-devel-ubuntu20.04镜像2如果使用了18.04的镜像nvidia/cuda:11.1.1-cudnn8-devel-ubuntu18.04可以使用我…...

JAVA线程池原理详解二

JAVA线程池原理详解二 一. Executor框架 Eexecutor作为灵活且强大的异步执行框架&#xff0c;其支持多种不同类型的任务执行策略&#xff0c;提供了一种标准的方法将任务的提交过程和执行过程解耦开发&#xff0c;基于生产者-消费者模式&#xff0c;其提交任务的线程相当于生…...

Java 常用 API

文章目录一、Math二、System三、Object1. toString() 方法2. equals() 方法四、Arrays1. 冒泡排序2. Arrays 常用方法五、基本类型包装类1. Integer2. int 和 String 相互转换3. 字符串中数据排序4. 自动装箱和拆箱六、日期类1. Date2. SimpleDateFormat3. Calendar4. 二月天一…...

记一次分布式环境下TOKEN实现用户登录

背景&#xff1a; ​ 以前的单体项目&#xff0c;使用的是session来保存用户登录状态&#xff0c;控制用户的登录过期时间等信息&#xff0c;但是这个session是只保存在该服务器的这个系统内存中。系统只有一个服务就没关系&#xff0c;但是如果是分布式的服务&#xff0c;每个…...

用cpolar发布本地的论坛网站 1

网页论坛向来是个很神奇的地方&#xff0c;曾经的天涯论坛和各种BBS&#xff0c;大家聚在在一起讨论某个问题&#xff0c;也能通过论坛发布想法&#xff0c;各种思维碰撞在一起&#xff0c;发生很多有趣的故事&#xff0c;也产生了很多流传一时的流行语录。当然&#xff0c;如果…...

CSS的4种引入方式

CSS的4种引入方式 目录CSS的4种引入方式一、内嵌式&#xff1a;CSS写在style标签中二、外联式&#xff1a;CSS写在一个单独的.css文件中三、行内式&#xff1a;CSS写在标签的style属性中四、导入外部样式五、css引用的优先级六、link和import的区别一、内嵌式&#xff1a;CSS写…...

Shell高级——Linux中的文件描述符(本质是数组的下标)

以下内容源于C语言中文网的学习与整理&#xff0c;非原创&#xff0c;如有侵权请告知删除。 前言 Linux中一切接文件&#xff0c;比如 C 源文件、视频文件、Shell脚本、可执行文件等&#xff0c;就连键盘、显示器、鼠标等硬件设备也都是文件。 一个 Linux 进程可以打开成百上…...

Nvidia jetson nano硬件架构

资料来源 官方文档中心 https://developer.nvidia.com/embedded/downloads -> 选jetson -> Jetson Nano Product Design Guide //产品设计指导(入口) //-> 1.1 References 列出了相关的文档 -> Jetson Nano Developer Kit Carrier Board Specification //板子标注…...

ffmpeg多路同时推流

一、ffmpeg常见使用方法1.1利用FFMPEG命令进行文件分割1.2转换格式1.3推流配置方法一&#xff1a;ngnix&#xff08;不推荐&#xff0c;推流不好使&#xff09;方法二&#xff1a;srs&#xff08;强烈推荐&#xff09;1.4查看nginx启动是否成功二、ffmpeg推流——>ngnix单路…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

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

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

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...