牛客 松鼠回家(二分答案+最短路)
题目描述
松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中,现在松鼠宝宝仅有h点体力,所有的边经过一次后会消耗部分体力,同时松鼠爸爸为了惩罚贪玩的松鼠宝宝,每到一个点会扣除部分松果(起点的松果也会扣除)。现松鼠宝宝向你求助,询问在能到达家的情况下
尽可能让路径上扣除松果的数量最大的那个点扣除的数量尽可能小。
输入描述:
第一行读入五个数n,m,st,ed, h(分别无向图的点数,边数,起点位置,家的位置,开始时候的体力)
接下来一行读入n个数ai(每个点所扣除的松果数量)
1<=n <=1e4
1<=m<= 2e4
1<=ai,z, h <= 1e7
1 <= x,y <= n
输出描述:
输出一行代表最大扣除数量的最小值,若无法到达,则输出-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条边的无向图中,现在松鼠宝宝仅有h点体力,所有的边经过一次后会消耗部分体力,同时松鼠爸爸为了惩罚贪玩的松鼠宝宝,每到一个点会扣除部分松果(起点的松果也会扣除&#…...
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第二节---双目地图初始化
比起单目初始化,而双目实现地图的初始化非常简单,只需要一帧(左右目图像)即可完成初始化。 行特征点统计。考虑用图像金字塔尺度作为偏移量,在当前点上下正负偏移量(r)内的纵坐标值都认为是匹配点可能存在…...
后端常使用的中间件知识点--持续更新
类型难度mysqlmysql中SQL优化:多角度分析包学包会,sql优化全过程,刨根分析redis多角度剖析redis数据结构及底层实现原理、应用场景MQ简单大体说明RabbitMQ的使用(简单版)mybatis使用JDBC的批量插入百万数据要多少秒一遍…...
非科班的大家如何顺滑转码
近年来,很多人想要从其他行业跳槽转入计算机领域。非计算机科班如何丝滑转码?请来聊聊你的看法和观点,我本身是信息与计算科学专业,周围的同学有不少也是被这个名字“骗过来的”,看这个名字都以为是计算机相关专业&…...
webpack中常见的Loader
目录 1.webpack中的loader是什么?配置方式 2. loader特性3.常见的loader 1.webpack中的loader是什么? loader 用于对模块的"源代码"进行转换,在 import 或"加载"模块时预处理文件 webpack做的事情,仅仅是分…...
RabbitMQ:可靠消息传递的强大消息中间件
消息中间件在现代分布式系统中起着关键作用,它们提供了一种可靠且高效的方法来进行异步通信和解耦。在这篇博客中,我们将重点介绍 RabbitMQ,一个广泛使用的开源消息中间件。我们将深入探讨 RabbitMQ 的特性、工作原理以及如何在应用程序中使用…...
python 批量下载m3u8的视频
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家:点击跳转 方法: 解析m3u8,获取其中的ts列表,多线程下载所有ts文件。 全部下完之后,用ffmpeg合…...
最后一击
第二届上海市青少年算法竞赛(小学组) 题目描述 Description 小爱和小艾两人组队打一只怪兽。一开始怪兽有 n 点生命值,当 n 变成 0 或更低时,怪兽就被消灭了。他们两人是同时开始攻击的,小爱每分钟可以攻击 a 下&…...
K8S资源管理方式
K8S资源管理方式 文章目录 K8S资源管理方式一、陈述式资源管理1.基础命令操作2.创建pod3.查看资源状态4.查看pod中的容器日志5.进入pod中的容器6.删除pod资源7.pod扩容8.项目生命周期管理(创建-->发布-->更新-->回滚-->删除)8.1创建services…...
第三章 图论 No.9有向图的强连通与半连通分量
文章目录 定义Tarjan求SCC1174. 受欢迎的牛367. 学校网络1175. 最大半连通子图368. 银河 定义 连通分量是无向图的概念,yxc说错了,不要被误导 强连通分量:在一个有向图中,对于分量中的任意两点u,v,一定能从…...
回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测
回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测 目录 回归预测 | MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输入单输出回归预测预测效果基本介绍模型描述程序设计参考…...
Mysql 和Oracle的区别
、mysql与oracle都是关系型数据库,Oracle是大型数据库,而MySQL是中小型数据库。但是MySQL是开源的,但是Oracle是收费的,而且比较贵。 1 2 mysql默认端口:3306,默认用户:root oracle默认端口&…...
在收藏夹里“积灰”的好东西——“收藏从未停止,行动从未开始”
方向一:分享一道你收藏的好题 小雅兰刚学数据结构与算法的时候,学的真的是很吃力,感觉链表真的特别的难,在学习了后面的知识之后,发现链表慢慢变得简单了,若是放在现在,小雅兰仍然觉得链表的知…...
【算法|数组】双指针
算法|数组——双指针 引入 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:…...
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. 螺旋矩阵 🔗 原题链接:54. 螺旋矩阵 类似于BFS那样使用方向数组即可。 class Solution { public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m matrix.size(), …...
小龟带你敲排序之冒泡排序
冒泡排序 一. 定义二.题目三. 思路分析(图文结合)四. 代码演示 一. 定义 冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元…...
Nacos AP架构集群搭建(Windows)
手写SpringCloud项目地址,求个star github:https://github.com/huangjianguo2000/spring-cloud-lightweight gitee:https://gitee.com/huangjianguo2000/spring-cloud-lightweigh 目录: 一:初始化MySQL 二:复制粘贴三份Nacos文…...
nodejs+vue+elementui,图书评论管理系统_g9e3a
用户的功能主要是对首页、图书信息、公告信息、在线咨询、个人中心等进行操作。表名:token语言 node.js 框架:Express 前端:Vue.js 数据库:mysql 数据库工具:Navicat 开发软件:VScode 前端nodejsvueelementui, 管理员…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
