算法进阶指南图论 通信线路

通信线路

在这里插入图片描述
思路:我们考虑需要升级的那条电缆的花费,若其花费为 w ,那么从 1 到 n 的路径上,至多存在 k 条路径的价值大于 w ,这具有一定的单调性,当花费 w 越大,我们路径上价值大于 w 的花费会越少,由此可以进行二分,求出我们所需要的最小花费。

考虑如何写check 函数,根据上面所说,如果从1-n的路径上,其花费大于 w的数量小于等于 k ,那么即为合法。由此我们可以转化为,对于从1-n路径上的边,若其边权大于 w,则为 1,否则为 0 ,由此就转化为了从1-n的最短路径长度是否小于等于k,运用dijk跑最短路即可,又因为是 0/1边权,所以可以使用双端队列进行优化,整体时间复杂度为 : n l o g n nlogn nlogn

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,m,k;vector<pll> e[N];
int d[N];
bool st[N];
bool check(int x)
{deque<int> q;memset(st,0,sizeof st);memset(d,0x3f,sizeof d);d[1]=0;q.push_front(1);while(!q.empty()){auto t=q.front();q.pop_front();if(st[t]) continue;st[t]=1;for(auto [u,w]: e[t]){w = w> x? 1: 0;if(d[u]>d[t]+w){d[u]=d[t]+w;if(w==1) q.push_back(u);else q.push_front(u);} }}return d[n]<=k;
}void solve()
{cin>>n>>m>>k;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});e[v].push_back({u,w});}int l=0,r=1e6+5;int ans=-1;while(l<=r){int mid=(l+r)/2;if(check(mid)){r=mid-1;ans=mid;}else l=mid+1;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

命令行远程操作windows

如遇安装python模块问题&#xff0c;请参考此连接处理&#xff1a;http://t.csdnimg.cn/l9W6f 一、命令行中使用ssh连接 1、安装 OpenSSH 客户端&#xff1a; 在 Windows 10 中&#xff0c;打开“设置”应用&#xff0c;选择“应用” > “可选功能” > “添加功能”。…

CCLINK IEFB总线转ETHERNET/IP网络的协议网关使欧姆龙和三菱的数据互通的简单配置方法

想要实现CCLINK IEFB总线和ETHERNET/IP网络的数据互通。 捷米JM-EIP-CCLKIE是一款ETHERNET/IP从站功能的通讯网关&#xff0c;该产品主要功能是实现CCLINK IEFB总线和ETHERNET/IP网络的数据互通。本网关连接到ETHERNET/IP总线和CCLINK IEFB总线上都可以做为从站使用。网关分别…

uni-app学习笔记(二)

目录 一、路由与页面跳转 1、tabar与普通页面跳转例子 2、navigateTo 3、switchTab 二、vue组件 1、传统vue组件的使用 2、easycom 三、uView组件库 1、安装配置 2、引入配置 3、使用 四、Vuex 1、认识 2、state基本使用 3、mapState使用 五、网络请求 1、封装…

云数据仓库实践:AWS Redshift在大数据储存分析上的落地经验分享

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…

【ChatGPT】人工智能的下一个前沿

&#x1f38a;专栏【ChatGPT】 &#x1f33a;每日一句&#xff1a;慢慢变好,我是,你也是 ⭐欢迎并且感谢大家指出我的问题 文章目录 一、引言 二、ChatGPT的工作原理 三、ChatGPT的主要特点 四、ChatGPT的应用场景 五、结论与展望 ​​​​​​​ 一、引言 随着人工智能技…

MyBatis(二)

3. MyBatis获取参数值的两种方式 两种方式&#xff1a;${}和#{} ${}的本质就是字符串拼接&#xff0c;#{}的本质就是占位符赋值${}使用字符串拼接的方式拼接sql&#xff0c;若为字符串类型或日期类型的字段进行赋值时&#xff0c;需要手动加单引号&#xff1b;但是#{}使用占位…

ClickHouse开发系列

一、 ClickHouse详解、安装教程_clickhouse源码安装 二、ClickHouse 语法详解_clickhouse讲解 三、ClickHouse SQL 操作语句详解 四、ClickHouse 高级教程—官方原版 五、ClickHouse主键索引最佳实践 六、MySQL与ClickHouse集成 七、ClickHouse 集成MongoDB、Re…

Yolov8部署——vs2019生成解决方案问题

Yolov8部署——vs2019生成解决方案问题 &#xff08;1&#xff09;Yolov8部署 最近开始在win10上部署Yolov8,并用tensorrt加速&#xff0c;从此贴开始记录后续遇到的部署问题。 &#xff08;2&#xff09;vs2019生成解决方案问题 报错如下图&#xff1a; NvInfer.h是Tenso…

基于SSM+Vue的随心淘网管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

BSP-STM32移植FreeRTOS

在stm32裸机工程中的Middlewares目录添加freeRtos源码 在裸机工程中的main中调用freertos接口

【JavaEESpring】认识Spring

认识Spring 1. 什么是框架2. SpringBoot 介绍2.1 Spring 的介绍2.2 SpringBoot 1. 什么是框架 框架(Framework) &#xff0c;意思是框架、机制、准则。通俗的来讲: 框架是实现某种功能的半成品, 他提供了⼀些常⽤的⼯具类, 我们在框架的基础上, 可以更加⾼效的进⾏开发 后端框…

docker搭建mysql环境

1. 基础环境 名称描述CentOS 7.6Linux操作系统版本docker 20.10.5docker版本mysql 8.0.29mysql镜像版本 2. 下载安装 使用docker命令下载mysql镜像 [rootzhouwei ~]# docker pull mysql:8.0.29查看docker仓库是否已经下载了mysql镜像 [rootzhouwei ~]# docker images将mys…

Java算法(六):模拟评委打分案例 方法封装抽离实现 程序的节流处理

Java算法&#xff08;六&#xff09; 评委打分 需求&#xff1a; 在编程竞赛中&#xff0c;有 6 个评委为参赛选手打分&#xff0c;分数为 0 - 100 的整数分。 选手的最后得分为&#xff1a;去掉一个最高分和一个最低分后 的 4个评委的平均值。 注意程序的节流 package c…

【 毕设项目源码推荐 javaweb 项目】 基于 springboot+vue 的图书个性化推荐系统的设计与实现(springboot003)

简介 :::warning 【 毕设项目源码推荐 javaweb 项目】 基于 springbootvue 的图书个性化推荐系统的设计与实现适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负…

【快速使用ShardingJDBC的哈希分片策略进行分库分表】

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容&#x1f34a;1.引入maven依赖&#x1f34a;2.启动类上添加注解MapperScan&#x1f34a;3.添加application.properties配置&#x1f34a;4.普通的自定义实体类&#x1f34a;5.写个测试类验证一下&#x1f34a;6.控制台打印…

c#如何把字符串中的指定字符删除

可以使用以下四种方法&#xff1a; 一、使用关键字&#xff1a;Replace public string Replace(char oldChar,char newChar); 在对象中寻找oldChar&#xff0c;如果寻找到&#xff0c;就用newChar将oldChar替换掉。 1、实例代码&#xff1a; 2、执行结果&#xff1a; 二、Rem…

洛谷P5731 【深基5.习6】蛇形方阵java版题解

import java.util.Arrays; import java.util.Scanner;// 给出一个不大于9的正整数n&#xff0c;输出nn的蛇形方阵。 public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[][] a new int[n][n];int total…

AWTK 与 Qt 的异同点比较

相似之处&#xff1a; 跨平台支持&#xff1a; AWTK 和 Qt 都提供了跨平台的支持&#xff0c;可以在多种操作系统上进行开发和部署&#xff0c;包括 Windows、Linux、macOS 等。丰富的组件库&#xff1a; 两者都提供了丰富的图形界面组件库&#xff0c;能够满足各种应用程序的…

在Google Kubernetes集群创建分布式Jenkins(二)

上一篇博客在Google Kubernetes集群创建分布式Jenkins(一)-CSDN博客我介绍了如何在GCP的K8S集群上部署一个分布式的Jenkins&#xff0c;并实现了一个简单的Pipeline的运行。 在实际的开发中&#xff0c;我们通常都会按照以下的CICD流程来设置Pipeline 在我司的实际实践中&…

Spring Cloud之多级缓存

目录 传统缓存 多级缓存 JVM进程缓存 Caffeine 缓存驱逐策略 实现进程缓存 常用Lua语法 数据类型 变量声明 循环使用 定义函数 条件控制 安装OpenResty 实现Nginx业务逻辑编写 请求参数解析 实现lua访问tomcat JSON的序列化和反序列化 Tomcat的集群负载均衡 …