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

2023-11-14 LeetCode每日一题(阈值距离内邻居最少的城市)

2023-11-14每日一题

一、题目编号

1334. 阈值距离内邻居最少的城市

二、题目链接

点击跳转到题目位置

三、题目描述

有 n 个城市,按从 0 到 n-1 编号。给你一个边数组 edges,其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边,距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市,则返回编号最大的城市。

注意,连接城市 ij 的路径的距离等于沿该路径的所有边的权重之和。

示例 1:
在这里插入图片描述

示例 2:
在这里插入图片描述
提示:

  • 2 <= n <= 100
  • 1 <= edges.length <= n * (n - 1) / 2
  • edges[i].length == 3
  • 0 <= fromi < toi < n
  • 1 <= weighti, distanceThreshold <= 104
  • 所有 (fromi, toi) 都是不同的。

四、解题代码

class Solution {#define maxn 101#define inf -1int Min(int a,int b){if(a==inf){return b;}if(b==inf){return a;}return a<b ? a:b;}int mat[maxn][maxn];int spfa(int n,int u,int dt){queue<int> q;int dist[maxn];memset(dist,inf,sizeof(dist));dist[u]=0;q.push(u);while(!q.empty()){u=q.front();q.pop();if(dist[u]>dt){continue;}for(int i=0;i<n;i++){if(mat[u][i] == inf){continue;}int todist=dist[u]+mat[u][i];if(dist[i]==inf || todist< dist[i]){dist[i]=todist;q.push(i);}}}int cnt=0;for(int i=0;i<n;i++){if(dist[i]!=inf && dist[i]<=dt){cnt++;}}return cnt;}public:int findTheCity(int n, vector<vector<int>>& edges, int dt) {memset(mat,inf,sizeof(mat));for(int i=0;i<edges.size();i++){int u=edges[i][0];int v=edges[i][1];int w=edges[i][2];mat[u][v]=mat[v][u]=Min(mat[u][v],w);}int Recnt=111;int index=-1;for(int i=n-1;i>=0;i--){int cnt=spfa(n,i,dt);if(cnt<Recnt){index=i;Recnt=cnt;}}return index;}
};

五、解题思路

(1) 最短路径问题,使用spfa算法解决。

相关文章:

2023-11-14 LeetCode每日一题(阈值距离内邻居最少的城市)

2023-11-14每日一题 一、题目编号 1334. 阈值距离内邻居最少的城市二、题目链接 点击跳转到题目位置 三、题目描述 有 n 个城市&#xff0c;按从 0 到 n-1 编号。给你一个边数组 edges&#xff0c;其中 edges[i] [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的…...

AdServices归因和iAd归因集成

AdServices framework 是 Apple 专门为 ASA 提供的归因框架 。尤其在ATT 政策推出以后&#xff0c;app 获取用户 IDFA 的比例大幅降低&#xff0c;传统的依靠IDFA 的方法也无法准确归因。 但是 Apple 为 ASA 开了一个后门&#xff0c;其他广告渠道无法获取用户的 IDFA 作为身份…...

关于 内部类 你了解多少?(详解!!)

目录 1. 什么是内部类&#xff1f; 2. 内部类的分类 3. 内部类 3.1 实例内部类 3.2 静态内部类 4. 局部内部类 5. 匿名内部类 6.对象的打印 “不积跬步无以至千里&#xff0c;不积小流无以成江海。”每天坚持学习&#xff0c;哪怕是一点点&#xff01;&#xff01;&a…...

CNVD-2021-09650:锐捷NBR路由器(guestIsUp.php)RCE漏洞复现 [附POC]

文章目录 锐捷NBR路由器guestIsUp.php远程命令执行漏洞(CNVD-2021-09650)复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 锐捷NBR路由器guestIsUp.php远程命令执行漏洞(CNVD-2021-09650)复现 [附POC] 0x01 前言 免…...

如何在Docker部署Draw.io绘图工具并远程访问

文章目录 前言1. 使用Docker本地部署Drawio2. 安装cpolar内网穿透工具3. 配置Draw.io公网访问地址4. 公网远程访问Draw.io 前言 提到流程图&#xff0c;大家第一时间可能会想到Visio&#xff0c;不可否认&#xff0c;VIsio确实是功能强大&#xff0c;但是软件为收费&#xff0…...

Android APK打包的过程主要步骤

Android APK打包的过程可以概括为以下几个主要步骤&#xff1a; 编译源代码&#xff1a;将开发好的Java源代码编译成Dalvik字节码文件&#xff08;.dex文件&#xff09;&#xff0c;Android安卓该文件包含了Android平台上的运行程序的指令集。打包资源文件&#xff1a;将应用程…...

吃透 Spring 系列—MVC部分

目录 ◆ SpringMVC简介 - SpringMVC概述 - SpringMVC快速入门 - Controller中访问容器中的Bean - SpringMVC关键组件浅析 ◆ SpringMVC的请求处理 - 请求映射路径的配置 - 请求数据的接收 - Javaweb常用对象获取 - 请求静态资源 - 注解驱动 标签 ◆ SpringMV…...

Java面试题(每天10题)-------连载(32)

目录 设计模式篇 1、工厂方法模式&#xff08;利用创建同一接口的不同实例&#xff09;&#xff1a; 2、抽象工厂模式&#xff08;多个工厂&#xff09; 3、单例模式&#xff08;保证对象只有一个实例&#xff09; 4、原型模式&#xff08;对一个原型进行复制、克隆产生类…...

HDP集群Kafka开启SASLPLAINTEXT安全认证

hdp页面修改kafka配置 java代码连接kafka增加对应的认证信息 props.put("security.protocol","SASL_PLAINTEXT");props.put("sasl.mechanism","PLAIN");props.put("sasl.jaas.config","org.apache.kafka.common.securi…...

判断上颌下颌的stl模型坐标轴是否正常

文章目录 研究方向:如何判断?又如何纠正?如何判断?Demo实现:先判断一个遍历相关文件夹下的所有病例如何纠正?Demo相关知识点研究方向:如何判断?又如何纠正? 如何判断? 当然,我们不能以坐标的正负来判断 我们看到这个Bounding Box里面有stl模型的xyz三轴方向的最大值与最…...

C/C++---------------LeetCode第1189. “气球” 的最大数量

气球的最大数量 题目及要求统计法在main内使用 题目及要求 给你一个字符串 text&#xff0c;你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”&#xff08;气球&#xff09;。 字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “ba…...

Arthas(阿尔萨斯)--(三)

目录 一、Arthas学习 1、class/classloader相关命令一 1、sc 2、sm 2、class/classloader相关命令二 1、jad 2、mc 3、redefine 三、class/classloader相关命令三 一、Arthas学习 Arthas(阿尔萨斯)--(一) Arthas(阿尔萨斯)--(二) 1、class/classloader相关命令一 …...

《变形监测与数据处理》笔记/期末复习资料(择期补充更新)

变形&#xff1a; 变形是物体在外来因素作用下产生的形状、大小及位置的变化&#xff08;随时间域和空间域的变化&#xff09;&#xff0c;它是自然界普遍存在的现象。 变形体&#xff1a; 一般包括工程建筑物、构筑物、大型机械设备以及其他自然和人工对象等。 变形体和变形…...

Linux:进程替换和知识整合

文章目录 进程程序替换替换原理进程替换的理解 环境变量与进程替换命令行解释器实现逻辑 进程程序替换 前面已经学习了子进程的创建&#xff0c;但是子进程的创建不管怎么说&#xff0c;都是父进程代码的一部分&#xff0c;那么实际上如果想要子进程执行新的程序呢&#xff1f…...

React组件在什么情况下会重新渲染

当我们使用React编写组件时&#xff0c;组件的重新渲染是一个重要的概念。重新渲染是指React组件在特定情况下会重新执行其渲染函数&#xff0c;更新用户界面以反映最新的数据。很多情况下&#xff0c;组件不必要的重新渲染会严重影响性能&#xff0c;所以要充分了解触发组件重…...

云ES容灾方案

一、ES集群可用性容灾 1.1 云ES集群可用性容灾(使用跨可用区实例) 云ES集群部署在三个可用区,单可用区故障,云ES集群依然可能对外提供服务;两个可用区故障,需要进行控制台切流(集群会自动切的选择主节点) 应用服务部署在二个可用区,单可用区故障,依然可对提供服务1.2 …...

Golang 中的 Context 包

简介 今天&#xff0c;我们将讨论 Go 编程中非常重要的一个主题&#xff1a;context 包。如果你现在觉得它很令人困惑&#xff0c;不用担心 — 在本文结束时&#xff0c;你将像专家一样处理 context&#xff01; 想象一下&#xff0c;你在一个主题公园&#xff0c;兴奋地准备…...

nginx服务器

nginx反向代理 nginx 反向代理的好处&#xff1a; 提高访问速度 因为nginx本身可以进行缓存&#xff0c;如果访问的同一接口&#xff0c;并且做了数据缓存&#xff0c; nginx就直接可把数据返回&#xff0c;不需要真正地访问服务端&#xff0c;从而提高访问速度。 进行负载均衡…...

电脑常用快捷键

一、Win键&#xff08;徽标键&#xff09; 以下是Windows操作系统中使用Win键&#xff08;徽标键&#xff09;结合A-Z的所有快捷方式描述&#xff1a; - Win A&#xff1a;打开操作中心&#xff0c;访问系统通知、快速设置和其他功能 - Win B&#xff1a;将焦点设置到任务栏…...

吴恩达《机器学习》8-3->8-4:模型表示I、模型表示II

8.3、模型表示I 一、大脑神经网络的基本原理 为了构建神经网络模型&#xff0c;首先需要理解大脑中的神经网络是如何运作的。每个神经元都可以被看作是一个处理单元或神经核&#xff0c;它包含多个输入&#xff08;树突&#xff09;和一个输出&#xff08;轴突&#xff09;。…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...