G - Road Blocked 2
G - Road Blocked 2
思路
只有当一条边是从 1 1 1到 n n n的所有最短路构成的图的桥时,去掉这条边,最短路才会变大
所以就可以用最短路加tarjan解决这道题了
怎么判断一条边是否可以构成最短路呢,比如求 1 1 1到 n n n的最短路,分别求出dist1(源点为1)和distn(源点为n),当一条边(端点分别为a,b,边长为w)包含再最短路之中时,它满足如下条件
dist1[n]=dist1[a]+w+distn[b]||dist1[n]=distn[a]+w+dist1[b]
当然还有其它方法,我写的代码就是其他方法,只是上面的方法更简单罢了
代码
struct Edge{int a,b,c;
};void solve() {int n,m;cin>>n>>m;vector<vector<pii>> g(n+1);vector<Edge> es(m+1);for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;es[i]={a,b,c};g[a].push_back({b,i}),g[b].push_back({a,i});}vector<bool> st(n+1);vector<ll> dist(n+1,1ll<<60);priority_queue<pll,vector<pll>,greater<pll>> q;dist[1]=0;q.push({dist[1],1});vector<vector<pii>> pas(n+1);while(q.size()){auto [dis,ver]=q.top();q.pop();if(st[ver]) continue;st[ver]=true;for(auto [y,id]:g[ver]){int w=es[id].c;if(dist[y]>dis+w){pas[y].clear();pas[y].push_back({ver,id});dist[y]=dis+w;q.push({dist[y],y}); }else if(dist[y]==dis+w){pas[y].push_back({ver,id});}}}vector<bool> st1(n+1);vector<vector<pii>> fg(n+1);auto dfs=[&](auto && self,int u)->void{if(st1[u]) return;st1[u]=true;for(auto [ver,id]:pas[u]){fg[u].push_back({ver,id}),fg[ver].push_back({u,id});self(self,ver);}};dfs(dfs,n);vector<int> dfn(n+1),low(n+1);vector<bool> fst(m+1);int timestamp=0;auto tarjan=[&](auto && self,int u,int fa)->void{dfn[u]=low[u]=++timestamp;for(auto [y,id]:fg[u]){if(!dfn[y]){self(self,y,u);low[u]=min(low[u],low[y]);if(low[y]>dfn[u]){fst[id]=true;}}else if(y!=fa){low[u]=min(low[u],dfn[y]);}}};tarjan(tarjan,1,0);for(int i=1;i<=m;i++){cout<<(fst[i]?"Yes":"No")<<endl;}
}
相关文章:
G - Road Blocked 2
G - Road Blocked 2 思路 只有当一条边是从 1 1 1到 n n n的所有最短路构成的图的桥时,去掉这条边,最短路才会变大 所以就可以用最短路加tarjan解决这道题了 怎么判断一条边是否可以构成最短路呢,比如求 1 1 1到 n n n的最短路࿰…...
R语言绘制Venn图(文氏图、温氏图、维恩图、范氏图、韦恩图)
Venn图,又称文氏图,标题中其他名字也是它的别称,由封闭圆形组成,代表不同集合。圆形重叠部分表示集合交集,非重叠处为独有元素。在生物学、统计学等领域广泛应用,可展示不同数据集相似性与差异,…...
【Vue.js】vue2 项目在 Vscode 中使用 Ctrl + 鼠标左键跳转 @ 别名导入的 js 文件和 .vue 文件
js 文件跳转 需要安装插件 Vetur 然后需要我们在项目根目录下添加 jsconfig.json 配置,至于配置的作用,可以参考我的另外一篇博客: 【React 】react 创建项目配置 jsconfig.json 的作用 它主要用于配置 JavaScript 或 TypeScript 项目的根…...
NVM配置与Vue3+Vite项目快速搭建指南
本文目录 1、配置环境1.1 NVM1、nvm常用命令 1.2 Mac配置环境1、安装nvm 1.3 Window配置环境1、安装nvm 2、 项目搭建2.1 项目依赖2.2 安装依赖2.3 配置1、别名配置2、创建样式及图片文件夹3、路由 2.4 项目搭建效果2.5 项目结构 在当今快速发展的前端技术领域中,掌…...
面试“利器“——微学时光
大家好,我是程序员阿药。微学时光是一款专为计算机专业学生和IT行业求职者设计的面试刷题小程序,它汇集了丰富的计算机面试题和知识点,旨在帮助用户随时随地学习和复习,提高自身的技术能力和面试技巧。 主题 随时随地学习&#x…...
【Unity】【游戏开发】游戏引擎是如何模拟世界的
【核心感悟】 游戏引擎通过两个维度的合并来模拟这个时间。 一个维度叫物理模型。 一个维度叫视觉模型。 对于物理模型,我们需要用物理引擎给予行为。 对于视觉模型,我们需要用动画去给予行为。 物理模型是真实机制,视觉模型是艺术表现&…...
vscode配置conda虚拟环境【windows系统】
安装好anacondavscode里安装python插件 3.点击左侧插件 如图1,再2,再点击3小星星激活conda环境 最后下方栏就出现conda环境了。就可以用啦...
libgpiod在imx8平台交叉编译说明
如下记录是在 imx8上测试使用 参考博主的文章 iMX6ULL 库移植 | Libgpiod 库的交叉编译及使用指南(linux) 编译说明 1: build.sh代码如下所示,先执行 source build.sh,注意修改交叉编译工具链为自己本地的地址; 2:执行 ./autogen…...
无人机之自主飞行关键技术篇
无人机自主飞行指的是无人机利用先进的算法和传感器,实现自我导航、路径规划、环境感知和自动避障等能力。这种飞行模式大大提升了无人机的智能化水平和操作的自动化程度。 一、传感器技术 传感器是无人机实现自主飞行和数据采集的关键组件,主要包括&a…...
performance.timing
performance.timing 是 Web 性能 API 的一部分,用于获取页面加载过程中的各个时间戳。这些时间戳可以帮助开发者分析页面加载性能,找出潜在的瓶颈。performance.timing 返回一个 PerformanceTiming 对象,该对象包含了多个属性,每个…...
教你不用下载 maven,不用配置环境变量,在 idea 上创建 maven 项目
我的主页:2的n次方_ 1. Maven Maven是⼀个项⽬管理⼯具, 通过 pom.xml ⽂件的配置获取 jar 包,⽽不⽤⼿动去添加 jar 包,这样就大大的提高了开发效率 2. Maven 的核心功能 2.1. 项目构建 创建第一个 Maven 项目 Maven 提供了标准的…...
linux 设置tomcat开机启动
在Linux系统中,要配置Tomcat开机自启动,可以创建一个名为 tomcat.service 的 systemd 服务文件,并将其放置在 /etc/systemd/system/ 目录下。以下是一个基本的服务文件示例,假设Tomcat安装在 /usr/local/tomcat 路径下:…...
opencv出错以及解决技巧
opencv配置 一开始,include的路径是<opencv4/opencv2/…> 这样在using namespace cv的时候导致了报错, 所以在cmakelist中需要对cmake的版本进行升级。 set(CMAKE_CXX_FLAGS “-stdc14 -O0 -Wall”)-O0 表示在编译过程中不进行任何优化 对应的pac…...
Python爬虫进阶(实战篇一)
接,基础篇,链接:python爬虫入门(所有演示代码,均有逐行分析!)-CSDN博客 目录 1.爬取博客网站全部文章列表 ps:补充(正则表达式) 爬虫实现 爬虫代码: 2.爬…...
运维面试题(2)
ssh服务(重点)协议使用 端口 号:默认是 22, 可以是被修改的,如果需要修改,则需要修改 ssh 服务的配置文件:#/etc/ssh/ssh_config,可以通过这个配置文件来修改端口 端口号可以修改&am…...
Django CSRF Token缺失或不正确
在Django中,CSRF(跨站请求伪造)验证失败,提示“CSRF token missing or incorrect”的错误,通常是由以下几个原因造成的: 忘记在表单中添加 {% csrf_token %} 模板标签:这是最常见的原因之一。确…...
10.12Python数学基础-矩阵(下)
9.矩阵的转置 矩阵的转置(Transpose)是矩阵操作中的一种基本运算。它通过交换矩阵的行和列来生成一个新的矩阵。具体来说,如果 A 是一个 mn 的矩阵,那么它的转置矩阵 A^T 是一个 nm 的矩阵,其中 A^T 的第 i 行第 j 列…...
vue网络自学知识点汇总
初体验 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><!--1.引入vue.j…...
Springboot项目Activemq延迟自定义消息完整代码案例(亲测可用)
1、porm.xml增加依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-activemq</artifactId> </dependency> 2、application.properties增加配置 # 连接地址 spring.activemq.broker-url=fa…...
常见ElasticSearch 面试题解析(上)
前言 ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsearch是用Java语言开发的,并作为Apache许可条款下的开放源码发布,是一种流行的企业级搜索引擎。ElasticSearch…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...
