当前位置: 首页 > 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, 管理员…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

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

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

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...