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

「3.3」虫洞 Wormholes

 多组数据不清零——见祖宗 

「3.3」虫洞 Wormholes

问题背景

「一本通3.3 练习2」

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。John 的每个农场有 M 条小路(无向边)连接着 N(从 1 到 N 标号)块地,并有 W 个虫洞。

现在 John 想借助这些虫洞来回到过去(在出发时刻之前回到出发点),请你告诉他能办到吗。 John 将向你提供 F 个农场的地图。没有小路会耗费你超过 10^4 秒的时间,当然也没有虫洞回帮你回到超过 10^4 秒以前。

输入格式

第一行一个整数 F,表示农场个数;
对于每个农场:
第一行,三个整数 N,M,W;
接下来 M 行,每行三个数 S,E,T,表示在标号为 S 的地与标号为 E 的地中间有一条用时 T 秒的小路;
接下来 W 行,每行三个数 S,E,T,表示在标号为 S 的地与标号为 E 的地中间有一条可以使 John 到达 T 秒前的虫洞。

输出格式

输出共 F 行,如果 John 能在第 i 个农场实现他的目标,就在第 i 行输出 YES,否则输出 NO。

样例输入1

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

样例输出1

NO
YES

注释说明

对于全部数据,1≤F≤5, 1≤N≤500, 1≤M≤2500, 1≤W≤200,1≤S,E≤N, ∣T∣≤10^4。

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[100005],a,b,c,huan[100005],w,t;
bool bl[100005];
struct ed {int to,w;
};
vector<ed>e[100005];
void spfa(int s){deque<int>q;memset(dis,0x3f,sizeof(dis));memset(bl,0,sizeof(bl));memset(huan,0,sizeof(huan));q.push_back(s);bl[s]=1;huan[s]++;dis[s]=0;while(!q.empty()) {int k=q.front();q.pop_front();bl[k]=0;int o;for(int i=0; i<e[k].size(); i++){o=e[k][i].to;if(e[k][i].w+dis[k]<dis[o]){dis[o]=e[k][i].w+dis[k];if(bl[o]==0){if(q.empty()||dis[o]<q.front())q.push_front(o);else q.push_back(o);bl[o]=1;huan[o]++;if(huan[o]>n){puts("YES");return;}}}}}puts("NO");
}
int main() {scanf("%d",&t);while(t--) {scanf("%d%d%d",&n,&m,&w);for (int i = 0; i <= 501; i++) e[i].clear();for(int i=1; i<=m; i++) {scanf("%d%d%d",&a,&b,&c);e[a].push_back((ed){b,c});e[b].push_back((ed){a,c});}for(int i=1; i<=w; i++) {scanf("%d%d%d",&a,&b,&c);e[a].push_back((ed){b,-c});}for (int i=1;i<=n;i++)e[0].push_back((ed){i,0});spfa(0);}
}
/*
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8NO
YES
*/

相关文章:

「3.3」虫洞 Wormholes

多组数据不清零——见祖宗 「3.3」虫洞 Wormholes 问题背景 「一本通3.3 练习2」 题目描述 John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边&#xff0c;并可以使你返回到过去的一个时刻&#xff08;相对你进入虫洞之前&#xff09;。John 的每…...

网页篡改防御方法

网页篡改防御方法 将服务器安全补丁升级到最新版 操作系统、应用程序、数据库等都需要使用最新的安全补丁&#xff0c;打补丁主要是为防止攻击者利用缓冲溢出和设计缺陷等进行攻击。 封闭未使用但已经开放的网络服务端口及未使用的服务 对于Windows Server 2003操作系统&am…...

Pikachu-Cross-Site Scripting-xss盲打

xss盲打&#xff0c;不是一种漏洞类型&#xff0c;而是一个攻击场景&#xff1b;在前端、或者在当前页面是看不到攻击结果&#xff1b;而是在后端、在别的页面才看到结果。 登陆后台&#xff0c;查看结果&#xff1b;...

JAVA思维提升案例5

抢红包案例&#xff1a; 要求&#xff1a; 一个大V直播时发起了抢红包活动&#xff0c;分别有&#xff1a;9、666、188、520、99999五个红包。 请模拟粉丝来抽奖&#xff0c;按照先来先得&#xff0c;随机抽取&#xff0c;抽完即止&#xff0c;注意&#xff1a;一个红包只能被…...

PostgreSQL的字符集

PostgreSQL的字符集 PostgreSQL 支持多种字符集&#xff08;character sets&#xff09;&#xff0c;也称为编码&#xff08;encoding&#xff09;。字符集决定了数据库存储和处理文本数据的方式。在创建数据库时&#xff0c;可以指定数据库的字符集&#xff0c;或者使用默认的…...

CUDA 参考文章

CUDA&#xff1a;NVCC编译过程和兼容性详解_nvcc把cuda代码转换成什么-CSDN博客https://blog.csdn.net/fb_help/article/details/80462853 1、CUDA&#xff1a;NVCC编译过程和兼容性详解 CUDA&#xff1a;NVCC编译过程和兼容性详解 https://codeyarns.com/2014/03/03/how-to-sp…...

强缓存和协商缓存的区别

强缓存和协商缓存是Web开发中用于优化页面加载性能的两种主要缓存机制&#xff0c;它们之间存在显著的区别。以下是对这两种缓存机制的详细比较&#xff1a; 一、定义与工作原理 强缓存 定义&#xff1a;强缓存是指在浏览器发送请求前&#xff0c;先检查本地缓存中是否存在可用…...

工控系统组成与安全需求分析

目录 工控系统安全威胁与需求分析工业控制系统安全需求分析 工控系统安全威胁与需求分析 工业控制系统是由各种控制组件监测组件数据处理与展示组件共同构成的&#xff0c;对工业生产过程进行控制和监控的业务流程管控系统。 就是现在有很多工厂&#xff0c;它比如说要生产鞋…...

C(十三)for、while、do - while循环的抉择 --- 打怪闯关情景

前言&#xff1a; 继C&#xff08;十&#xff09;for循环 --- 黑神话情景之后&#x1f449; https://blog.csdn.net/2401_87025655/article/details/142684637 今天&#xff0c;杰哥想用一个打怪闯关的场景让与大家一起初步认识一下for、while、do - while循环的抉择。&#xf…...

【Android 源码分析】Activity生命周期之onStop-2

忽然有一天&#xff0c;我想要做一件事&#xff1a;去代码中去验证那些曾经被“灌输”的理论。                                                                                  – 服装…...

SpringCloudStream+RocketMQ多topic

之前写过两篇关于SpringCloudStream文章 spring-cloud-stream版本升级&#xff0c;告别旧注解EnableBinding&#xff0c;拥抱函数式编程_spring-cloud-stream output注解没有了-CSDN博客 SpringCloudStreamRocketMQ事务消息配置_spring-cloud-starter-stream-rocketmq-CSDN博…...

随记 前端框架React的初步认识

区分语言 像js 就是构建的最基本的 React框架和Vue框架&#xff0c;用自己的话来说的话&#xff0c;就是对js进行了一层封装&#xff0c;使使用js更加的方便 但是&#xff0c;React框架和Vue框架又不能这么简单的理解&#xff0c;因为这些框架里还封装了一些其他的东西。 向…...

数据结构 ——— 单链表oj题:链表分割(带哨兵位单向不循环链表实现)

目录 题目要求 手搓简易单链表 代码实现 题目要求 现有一链表的头指针 ListNode* head &#xff0c;给一定值 x &#xff0c;编写一段代码将所有小于 x 的节点排在其余节点之前&#xff0c;且不能改变原来的数据顺序&#xff0c;返回重新排列后的链表的头节点 举例说明&a…...

华为 HCIP-Datacom H12-821 题库 (32)

&#x1f423;博客最下方微信公众号回复题库,领取题库和教学资源 &#x1f424;诚挚欢迎IT交流有兴趣的公众号回复交流群 &#x1f998;公众号会持续更新网络小知识&#x1f63c; 1.当一个运行 MSTP 协议的交换设备端口收到一个配置BPDU 时&#xff0c;会与设备保存的全局配…...

[C++][第三方库][brpc]详细讲解

目录 1.介绍2.安装3.类与接口介绍1.日志输出类与接口2.ProtoBuf类与接口3.服务端类与接口4.客户端类与接口 4.使用0.一般流程1.Server2.客户端 -- 同步调用3.客户端 -- 异步调用 1.介绍 brpc是用C编写的工业级RPC框架&#xff0c;常用于搜索、存储、机器学习、广告、推荐等高性…...

Python-Learning

补充不熟悉的python知识 1 **是表示平方 注释是用来阐述代码要做什么&#xff0c;以及是如何做的 先编写行之有效的代码&#xff0c;再决定是对其做进一步改进&#xff0c;还是转而去编写新代码 列表常用是append&#xff0c;但也有pop&#xff0c;这个pop是输出一个值&…...

如何让 Android 的前端页面像 iOS 一样“优雅”?

作者:方英杰&#xff08;崇之&#xff09; 最近在调研前端页面适配 Android 端异形屏的方案&#xff0c;调研过程中发现了一些比较有意思的点&#xff0c;本文主要是做一个总结。 一、提出问题 首先&#xff0c;我们需要知道 Android 上的前端适配面临着什么问题。 问题其实很…...

10.3学习

1.循环依赖 循环依赖其实就是循环引用&#xff0c;也就是两个或者两个以上的 Bean 互相持有对方&#xff0c;最终形成闭环。比如A 依赖于B&#xff0c;B又依赖于A Spring中循环依赖场景有: prototype 原型 bean循环依赖 构造器的循环依赖&#xff08;构造器注入&#xff09;…...

Shell文本处理(三)

Shell文本处理三:字符串处理 1、字符串截取(切片)2、字符串替换3、字符串删除4、去除空格5、大小写转换6、字符串分割7、去除中文在Shell中,字符串没有单独的数据类型,一切都是变量。但这并不意味着我们不能像在Java、Python等其他编程语言中那样处理字符串 1、字符串截取…...

5个python多线程简单示例

示例 1: 基本线程创建 # 示例 1: 基本线程创建 import threading import timedef print_numbers():for i in range(5):time.sleep(1)print(i)# 创建线程 thread threading.Thread(targetprint_numbers)# 启动线程 thread.start()# 等待线程完成&#xff08;可选&#xff09; …...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...