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

牛客 松鼠回家(二分答案+最短路)

题目描述

松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中,现在松鼠宝宝仅有h点体力,所有的边经过一次后会消耗部分体力,同时松鼠爸爸为了惩罚贪玩的松鼠宝宝,每到一个点会扣除部分松果(起点的松果也会扣除)。现松鼠宝宝向你求助,询问在能到达家的情况下

        尽可能让路径上扣除松果的数量最大的那个点扣除的数量尽可能小。

输入描述:

第一行读入五个数n,m,st,ed, h(分别无向图的点数,边数,起点位置,家的位置,开始时候的体力)

接下来一行读入n个数ai(每个点所扣除的松果数量)

接下来m行读入x,y,z(分别代表无向边的两点和路上所消耗的体力)

1<=n <=1e4 

1<=m<= 2e4

1<=ai,z, h <= 1e7  

1 <= x,y <= n

输出描述:

输出一行代表最大扣除数量的最小值,若无法到达,则输出-1

示例1

输入

4 4 1 4 8
8
5
6
10
1 3 4
2 4 1
2 1 2
3 4 3

输出

10

学习学长用bfs来写最短路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int M=4e4+10;
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool st[N];
ll val[N];
ll dist[N];
vector<PII> v[N];
ll n,m,s,e,k,h,mx;
bool check(ll x)
{queue<ll> q;q.push(s);for(int i=1;i<=n;i++) dist[i]=INF,st[i]=false;dist[s]=0;while(q.size()){ll u=q.front();q.pop();st[u]=false;for(int i=0;i<v[u].size();i++){ll j=v[u][i].first;ll w=v[u][i].second;if(val[j]>x) continue;if(dist[j]>dist[u]+w){dist[j]=dist[u]+w;if(!st[j]){st[j]=true;q.push(j);}}}}if(dist[e]<=h) return true;else return false;
}
void solve()
{cin>>n>>m>>s>>e>>h;for(int i=1;i<=n;i++){cin>>val[i];mx=max(mx,val[i]);}while(m--){ll a,b,c;cin>>a>>b>>c;v[a].push_back({b,c});v[b].push_back({a,c});}ll l=0,r=mx;ll mid;while(l<r){mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}if(check(l))cout<<l<<endl;elsecout<<-1<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}

相关文章:

牛客 松鼠回家(二分答案+最短路)

题目描述 松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中&#xff0c;现在松鼠宝宝仅有h点体力&#xff0c;所有的边经过一次后会消耗部分体力&#xff0c;同时松鼠爸爸为了惩罚贪玩的松鼠宝宝&#xff0c;每到一个点会扣除部分松果&#xff08;起点的松果也会扣除&#…...

Mysql in 查询的奇怪方向

Mysql in 查询的奇怪方向 关于表字段存储的数据为 num1,num2,num3时, 还要通过多个num1,num2入参针对该字段进行查询 建表语句 CREATE TABLE test (test_ids varchar(100) DEFAULT NULL COMMENT 保存ids 以逗号分隔 ) ENGINEInnoDB;数据项 查询语句 SELECT test_ids FROM t…...

ORB-SLAM2第二节---双目地图初始化

比起单目初始化&#xff0c;而双目实现地图的初始化非常简单&#xff0c;只需要一帧&#xff08;左右目图像&#xff09;即可完成初始化。 行特征点统计。考虑用图像金字塔尺度作为偏移量&#xff0c;在当前点上下正负偏移量&#xff08;r)内的纵坐标值都认为是匹配点可能存在…...

后端常使用的中间件知识点--持续更新

类型难度mysqlmysql中SQL优化&#xff1a;多角度分析包学包会&#xff0c;sql优化全过程&#xff0c;刨根分析redis多角度剖析redis数据结构及底层实现原理、应用场景MQ简单大体说明RabbitMQ的使用&#xff08;简单版&#xff09;mybatis使用JDBC的批量插入百万数据要多少秒一遍…...

非科班的大家如何顺滑转码

近年来&#xff0c;很多人想要从其他行业跳槽转入计算机领域。非计算机科班如何丝滑转码&#xff1f;请来聊聊你的看法和观点&#xff0c;我本身是信息与计算科学专业&#xff0c;周围的同学有不少也是被这个名字“骗过来的”&#xff0c;看这个名字都以为是计算机相关专业&…...

webpack中常见的Loader

目录 1.webpack中的loader是什么&#xff1f;配置方式 2. loader特性3.常见的loader 1.webpack中的loader是什么&#xff1f; loader 用于对模块的"源代码"进行转换&#xff0c;在 import 或"加载"模块时预处理文件 webpack做的事情&#xff0c;仅仅是分…...

RabbitMQ:可靠消息传递的强大消息中间件

消息中间件在现代分布式系统中起着关键作用&#xff0c;它们提供了一种可靠且高效的方法来进行异步通信和解耦。在这篇博客中&#xff0c;我们将重点介绍 RabbitMQ&#xff0c;一个广泛使用的开源消息中间件。我们将深入探讨 RabbitMQ 的特性、工作原理以及如何在应用程序中使用…...

python 批量下载m3u8的视频

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;点击跳转 方法&#xff1a; 解析m3u8&#xff0c;获取其中的ts列表&#xff0c;多线程下载所有ts文件。 全部下完之后&#xff0c;用ffmpeg合…...

最后一击

第二届上海市青少年算法竞赛&#xff08;小学组&#xff09; 题目描述 Description 小爱和小艾两人组队打一只怪兽。一开始怪兽有 n 点生命值&#xff0c;当 n 变成 0 或更低时&#xff0c;怪兽就被消灭了。他们两人是同时开始攻击的&#xff0c;小爱每分钟可以攻击 a 下&…...

K8S资源管理方式

K8S资源管理方式 文章目录 K8S资源管理方式一、陈述式资源管理1.基础命令操作2.创建pod3.查看资源状态4.查看pod中的容器日志5.进入pod中的容器6.删除pod资源7.pod扩容8.项目生命周期管理&#xff08;创建-->发布-->更新-->回滚-->删除&#xff09;8.1创建services…...

第三章 图论 No.9有向图的强连通与半连通分量

文章目录 定义Tarjan求SCC1174. 受欢迎的牛367. 学校网络1175. 最大半连通子图368. 银河 定义 连通分量是无向图的概念&#xff0c;yxc说错了&#xff0c;不要被误导 强连通分量&#xff1a;在一个有向图中&#xff0c;对于分量中的任意两点u&#xff0c;v&#xff0c;一定能从…...

回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测

回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测 目录 回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测预测效果基本介绍模型描述程序设计参考…...

Mysql 和Oracle的区别

、mysql与oracle都是关系型数据库&#xff0c;Oracle是大型数据库&#xff0c;而MySQL是中小型数据库。但是MySQL是开源的&#xff0c;但是Oracle是收费的&#xff0c;而且比较贵。 1 2 mysql默认端口&#xff1a;3306&#xff0c;默认用户&#xff1a;root oracle默认端口&…...

在收藏夹里“积灰”的好东西——“收藏从未停止,行动从未开始”

方向一&#xff1a;分享一道你收藏的好题 小雅兰刚学数据结构与算法的时候&#xff0c;学的真的是很吃力&#xff0c;感觉链表真的特别的难&#xff0c;在学习了后面的知识之后&#xff0c;发现链表慢慢变得简单了&#xff0c;若是放在现在&#xff0c;小雅兰仍然觉得链表的知…...

【算法|数组】双指针

算法|数组——双指针 引入 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&#xff1a;…...

asp.net core6 webapi 使用反射批量注入接口层和实现接口层的接口的类到ioc中

IBLL接口层类库 namespace IBLL {public interface ICar{string CarName();} } namespace IBLL {public interface IRed{string RedName();} }BLL实现接口层类库 namespace BLL {public class Car : ICar{public string CarName(){return "BBA";}} } namespace BLL…...

【2023】字节跳动 10 日心动计划——第九关

目录 1. 螺旋矩阵2. 划分字母区间3. 子集 II 1. 螺旋矩阵 &#x1f517; 原题链接&#xff1a;54. 螺旋矩阵 类似于BFS那样使用方向数组即可。 class Solution { public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m matrix.size(), …...

小龟带你敲排序之冒泡排序

冒泡排序 一. 定义二.题目三. 思路分析&#xff08;图文结合&#xff09;四. 代码演示 一. 定义 冒泡排序&#xff08;Bubble Sort&#xff0c;台湾译为&#xff1a;泡沫排序或气泡排序&#xff09;是一种简单的排序算法。它重复地走访过要排序的数列&#xff0c;一次比较两个元…...

Nacos AP架构集群搭建(Windows)

手写SpringCloud项目地址&#xff0c;求个star github:https://github.com/huangjianguo2000/spring-cloud-lightweight gitee:https://gitee.com/huangjianguo2000/spring-cloud-lightweigh 目录&#xff1a; 一&#xff1a;初始化MySQL 二&#xff1a;复制粘贴三份Nacos文…...

nodejs+vue+elementui,图书评论管理系统_g9e3a

用户的功能主要是对首页、图书信息、公告信息、在线咨询、个人中心等进行操作。表名&#xff1a;token语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;VScode 前端nodejsvueelementui, 管理员…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...