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

相对论大师-记录型正负性质BFS/图论-链表/数据结构

看到这一题我的第一个思路就是双向bfs

起点是a,终点还是a,但是flag是相反的(“越”的方向)

tip1.可以用字典vis来存储flag

刚开始初始化时vissta,visend一个对应0、1                                        

要求两个队列相接的时候flag要相同

tip2.get_nei函数

读取输入的时候用字典存储了点之间的关系

那么get_nei的时候就需要返回可能的下个节点以及new_flag

                                    new_flag还是在外面判断,因为读取输入的时候是用0表示同向,1表示反向

tip3.存储中间过程

由于触碰点是起点和终点中间,所以我们需要记录前驱节点从而进行回溯

那么最适合的就是链表

from collections import deque,defaultdictd=defaultdict(set)n=int(input())for i in range(n):a,n1,b,n2=input().split()if n1==n2:d[a].add((b,0))#明显不能双向:否则会Yu 1 Yuci 0 Yuci 0 Yu 0 = Yu 1 Yu 0#d[b].add((a,0))#双向图?else:d[a].add((b,1))#d[b].add((a,1))def get_nei(cur):neis=d[cur]return neisdef bfs(k):sta=end=kstaq=deque([sta])endq=deque([end])vissta={sta:1}#用0,1表示相对性visend={end:0}presta={sta:None}#记录前驱节点preend={end:None}while staq and endq:ls=len(staq)le=len(endq)if ls<=le:for _ in range(ls):#当前层cur=staq.popleft()flag=vissta[cur]for nei,k in get_nei(cur): #解包if k:nflag= flag #0,1间取反else:nflag=not flagif nei not in vissta:vissta[nei]=nflagstaq.append(nei)presta[nei]=curif nei in visend and visend[nei]==vissta[nei]:return build_path(nei,presta,preend)else:for _ in range(le):cur=endq.popleft()flag=visend[cur]for nei,k in get_nei(cur):if k:nflag=not flag #0,1间取反else:nflag=flagif nei not in visend:visend[nei]=nflagendq.append(nei)preend[nei]=curif nei in vissta and vissta[nei]==visend[nei]:return build_path(nei,presta,preend)return 0def build_path(meet,presta,preend):path_sta=[]cur=meetwhile cur is not None:#开始链表回溯path_sta.append(cur)cur=presta[cur]path_sta.reverse()#掉头,方面后面衔接path_end=[]cur=preend[meet]while cur is not None:path_end.append(cur)cur=preend[cur]return path_sta+path_endprint(d)for i in d:k=bfs(i)print(k)'''不能dfs:不知道何时停止
def dfs()
'''

但是这段代码其实是错的,因为d[x]存的是x后面的节点,是单向的,那么就用不了双向 

from collections import deque
from collections import defaultdictd = defaultdict(list)n = int(input())
for _ in range(n):a, a_flag, b, b_flag = input().split()a_flag = int(a_flag)b_flag = int(b_flag)d[(a, a_flag)].append((b, b_flag))shortest_path = Nonenodes = set()
for key in d:nodes.add(key[0])for b, _ in d[key]:nodes.add(b)
nodes = list(nodes)for sta in nodes:for start_flag in [0, 1]:target_flag = 1 - start_flagvissta = {}staq = deque()staq.append((sta, start_flag, []))vissta[(sta, start_flag)] = Truefound = Falsewhile staq and not found:cur, flag, path_edges = staq.popleft()if cur == sta and flag == target_flag:if shortest_path is None or len(path_edges) < len(shortest_path):shortest_path = path_edgesfound = Truebreakfor (nei, nei_flag) in d.get((cur, flag), []):if (nei, nei_flag) not in vissta:vissta[(nei, nei_flag)] = Truenew_path = path_edges + \[(cur, flag, nei, nei_flag)]staq.append((nei, nei_flag, new_path))if found and len(shortest_path) == 0:break if shortest_path and len(shortest_path) == 0:break output_steps = []
for step in shortest_path:a, a_flag, b, b_flag = stepoutput_steps.append(f"{a} {a_flag} {b} {b_flag}")sta = shortest_path[0][0]
start_flag = shortest_path[0][1]
end_flag = 1 - start_flagprint(f"{' '.join(output_steps)} = {sta} {start_flag} {sta} {end_flag}")

相关文章:

相对论大师-记录型正负性质BFS/图论-链表/数据结构

看到这一题我的第一个思路就是双向bfs 起点是a&#xff0c;终点还是a&#xff0c;但是flag是相反的&#xff08;“越”的方向&#xff09; tip1.可以用字典vis来存储flag 刚开始初始化时vissta,visend一个对应0、1 要求两个队列相…...

代理设计模式:从底层原理到源代码的详细解释

代理设计模式&#xff08;Proxy Pattern&#xff09;是一种结构型设计模式&#xff0c;它通过创建一个代理对象来控制对目标对象的访问。代理对象充当客户端和目标对象之间的中介&#xff0c;允许在不修改目标对象的情况下添加额外的功能&#xff08;如权限控制、日志记录、延迟…...

EasyRTC音视频实时通话:打造高清低延迟的远程会议新生态

一、项目背景​ 随着数字化办公的普及&#xff0c;远程会议成为企业、教育机构、政府部门等组织跨地域协作沟通的重要方式。传统远程会议系统在音视频质量、低延迟传输、多平台兼容性等方面存在不足&#xff0c;难以满足用户对高清、流畅、稳定会议体验的需求。EasyRTC作为一款…...

零基础上手Python数据分析 (21):图表选择困难症?常用可视化类型详解与应用场景指南

写在前面 —— 告别盲目绘图,理解图表语言,为你的数据找到最佳“代言人” 在前面几篇博客中,我们已经学习了使用 Matplotlib 和 Seaborn 这两大 Python 可视化利器来绘制各种图表。我们掌握了创建折线图、柱状图、散点图、箱线图等常用图表的技术。然而,仅仅知道 如何 绘…...

HarmonyOS Next 编译之如何使用多目标产物不同包名应用

引言 在日常的开发中涉及到多签名和多产物构建输出时手动切换签名文件和包名在开发中是容易出错且费时的一个操作&#xff0c;鸿蒙提供了自定义hvigor插件和多目标产物构建&#xff0c;那我们可以通过hvigor插件来动态修改不同项目配置所需要的代码&#xff0c;保证一套代码在…...

Oracle Database Resident Connection Pooling (DRCP) 白皮书阅读笔记

本文为“Extreme Oracle Database Connection Scalability with Database Resident Connection Pooling (DRCP)”的中文翻译加阅读笔记。觉得是重点的就用粗体表示了。 白皮书版本为March 2025, Version 3.3&#xff0c;副标题为&#xff1a;Optimizing Oracle Database resou…...

Sharding-JDBC 系列专题 - 第七篇:Spring Boot 集成与 Sharding-Proxy 简介

Sharding-JDBC 系列专题 - 第七篇:Spring Boot 集成与 Sharding-Proxy 简介 本系列专题旨在帮助开发者全面掌握 Sharding-JDBC,一个轻量级的分布式数据库中间件。本篇作为系列的第七篇文章,将重点探讨 Sharding-JDBC 与 Spring Boot 的集成,以及 Sharding-Proxy 的基本概念…...

day30 学习笔记

文章目录 前言一、凸包特征检测1.穷举法2.QuickHull法 二、图像轮廓特征查找1.外接矩形2.最小外接矩形3.最小外接圆 前言 通过今天的学习&#xff0c;我掌握了OpenCV中有关凸包特征检测&#xff0c;图像轮廓特征查找的相关原理和操作 一、凸包特征检测 通俗的讲&#xff0c;凸…...

变更管理 Change Management

以下是关于项目管理中 变更管理 的深度解析,结合高项(如软考高级信息系统项目管理师)教材内容,系统阐述变更管理的理论框架、流程方法及实战应用: 一、变更管理的基本概念 1. 定义 变更管理是对项目范围、进度、成本、质量等基准的修改进行系统性控制的过程,旨在确保变…...

PaddlePaddle线性回归详解:从模型定义到加载,掌握深度学习基础

目录 前言一、paddlepaddle框架的线性回归1.1 paddlepaddle模型的定义方式1.1.1 使用序列的方式 nn.Sequential 组网1.1.2 使用类的方式 class nn.Layer组网1.2 数据加载 1.3 paddlepaddle模型的保存1.3.1 基础API保存1.3.2 高级API模型的保存1.3.2.1 训练fit进行保存1.3.2.2 …...

几种Word转换PDF的常用方法

使用 Word 内置功能 步骤&#xff1a;打开需要转换的 Word 文档&#xff0c;点击左上角的 “文件” 菜单&#xff0c;选择 “另存为”&#xff0c;选择保存位置&#xff0c;在 “保存类型” 下拉菜单中选择 “PDF”&#xff0c;点击 “保存” 按钮即可。适用场景&#xff1a;适…...

【美化vim】

美化vim 涉及文件一个例子 涉及文件 ~/.vimrc修改这个文件即可 一个例子 let mapleader ,set number " 显示行号"set relativenumber " 显示相对行号set incsearch " 实时开启搜索高亮set hlsearch " 搜索结果高亮set autoinden…...

【git】subtree拆分大的git库到多个独立git库

【git】subtree拆分大的git库到多个独立git库 一、拆分一个子目录为独立仓库 # 这就是那个大仓库 big-project git clone gitgithub.com:tom/big-project.git cd big-project# 把所有 eiyo 目录下的相关提交整理为一个新的分支 eiyo_code git subtree split -P eiyo -b eiyo_…...

Elasticsearch 使用reindex进行数据同步或索引重构

1、批量复制优化 POST _reindex {"source": {"index": "source","size": 5000},"dest": {"index": "dest"} }2、提高scroll的并行度优化 POST _reindex?slices5&refresh {"source": {…...

JDBC对数据的增删改查操作:从Statement到PrepareStatement

目录 一 . Statement简介 二. 通过Statement添加数据 1. 创建表 2. 通过Statement添加数据 a. 获取连接 b. 获取Statement对象 c. 定义SQL语句 d. 执行SQL语句 e. 关闭资源 3. 通过Statement修改数据 4. 通过Statement删除数据 三. PreparedStatement的使用(重点) …...

智体OS上线智体管家:对话式智体应用商店访问

DTNS.OS 更新公告 - 智体管家功能发布 &#x1f31f; 2024年4月22日重要更新&#xff1a;智体管家正式上线 智体管家是智体OS推出的全新功能&#xff0c;旨在让用户通过自然对话轻松发现和使用智体节点上的所有智体应用&#xff0c;相当于为智体网络打造了一个智能化的应用商…...

vscode flutter 插件, vscode运行安卓项目,.gradle 路径配置

Flutter Flutter Widget Snippets Awesome Flutter Snippets i dart-import Dart Data Class Generator Json to Dart Model Dart Getters And Setter GetX Snippets GetX Generator GetX Generator for Flutter flutter-img-syncvscode运行安卓项目&#xff0c;.gradle 路径配…...

dolphinscheduler实现(oracle-hdfs-doris)数据ETL

dolphinscheduler执行 完整脚本(自行替换相关变量)配置文件conf配置文件解析脚本转base64脚本 完整脚本(自行替换相关变量) user_olsh conf/getInfo.sh Oracle user conf/databases.conf password_olsh conf/getInfo.sh Oracle password conf/databases.conf dblink_olsh conf…...

ViewBS 的工作流程

ViewBS ViewBS 的工作流程 ViewBS 提供多个顶级命令,用于确定所需和最优参数。这些命令可分为两部分:甲基化报告和功能区域的数据可视化。 在甲基化报告部分中,提供多个顶级命令,可以生成关于读取覆盖度、甲基化水平分布、全局甲基化水平等报告。 在功能区域可视化部分…...

qt调用deepseek的API开发(附带源码)

今天讲的是使用qt做一个界面&#xff08;负责接受deepseek返回的数据和客户发送数据的端口&#xff09;会用流的方式接受数据提高用户体验 测试效果源码流程配置deepseek调用思路deepseek与qt联合开发界面思路 上一篇文章用的不是流开发&#xff0c;会让客户等待很久&#xff0…...

java中值传递的含义

Java 中的值传递&#xff08;Pass by Value&#xff09;详解 在 Java 中&#xff0c;所有参数的传递都是值传递&#xff08;Pass by Value&#xff09;&#xff0c;但根据传递的数据类型不同&#xff08;基本类型 vs 引用类型&#xff09;&#xff0c;表现行为会有所不同。 1.…...

【自然语言处理与大模型】如何知道自己部署的模型的最大并行访问数呢?

当你自己在服务器上部署好一个模型后&#xff0c;使用场景会有两种。第一种就是你自己去玩&#xff0c;结合自有的数据做RAG等等&#xff0c;这种情况下一般是不会考虑并发的问题。第二种是将部署好的服务给到别人来使用&#xff0c;这时候就必须知道我的服务到底支持多大的访问…...

基于PHP+MySQL实现(Web)单词助手网站

WordHelper 这是一个学习 PHP 的时候依照课程设计的要求&#xff0c;做的一个简单的单词助手。 系统通过 CDN 引入 Vue.js 和 ElementUI&#xff0c;并用 PHP 搭建了一个十分十分简易的后台。 一、设计要求 1、词汇录入与编辑。提供接口让用户录入英文单词、词义、发音、词…...

Java面试实战:谢飞机的求职记 - Spring Boot、Redis与微服务技术问答解析

场景描述 谢飞机&#xff0c;一位自称为“Java全栈大师”的程序员&#xff0c;参加了某互联网大厂的Java开发岗位面试。面试官严肃而专业&#xff0c;针对Spring Boot、Redis缓存以及微服务架构等核心技术展开提问。以下是谢飞机在面试中的表现。 第一轮提问&#xff08;基础篇…...

【数字图像处理】立体视觉信息提取

双目立体视觉原理 设一个为参考平面&#xff0c;一个为目标平面。增加了一个摄像头后&#xff0c;P与Q在目标面T上有分别的成像点 双目立体视觉&#xff1a;从两个不同的位置观察同一物体&#xff0c;用三角测量原理计算摄像机到该物体的距离的 方法 原理&#xff1a;三角测量…...

解析芯片低功耗设计的底层逻辑与实现方法

芯片低功耗设计的必要性可以从实际需求和技术优化两方面来探讨&#xff1a; 从需求角度看&#xff0c;工艺进步和应用场景共同驱动低功耗设计。 随着CMOS制程持续微缩&#xff0c;晶体管密度和时钟频率提升导致静态功耗显著增加&#xff0c;漏电流问题在先进工艺中尤为明显。…...

uniapp开发2--uniapp中的条件编译总结

以下是对 uni-app 中条件编译的总结&#xff1a; 概念&#xff1a; 条件编译是一种技术&#xff0c;允许你根据不同的平台或环境&#xff0c;编译不同的代码。 在 uni-app 中&#xff0c;这意味着你可以编写一套代码&#xff0c;然后根据要编译到的平台&#xff08;例如微信小…...

Netty 异步机制深度解析:Future 与 Promise 的前世今生

引言&#xff1a;异步编程的「糖」与「痛」 在高性能网络编程中&#xff0c;「异步」几乎是必备的设计模式&#xff0c;异步的好处就是可以提升系统吞吐量&#xff0c;提升效率。但很多开发者初入 Netty 时&#xff0c;对它的异步机制总有点模糊&#xff1a; 为什么 ChannelF…...

如何查看MySql主从同步的偏移量

1.Mysql的主从同步方案 mysql为了在实现读写分离&#xff0c;主库写&#xff0c;从库读 mysql的同步方案主要是通过从库读取主库的binlog日志的方式。 binlog就是一个记录mysql的操作的日志记录&#xff0c;从库通过拿到主库的binlog知道主库进行了哪些操作&#xff0c;然后在从…...

短信验证码安全实战:三网API+多语言适配开发指南

在短信服务中&#xff0c;创建自定义签名是发送通知、验证信息和其他类型消息的重要步骤。万维易源提供的“三网短信验证码”API为开发者和企业提供了高效、便捷的自定义签名创建服务&#xff0c;可以通过简单的接口调用提交签名给运营商审核。本文将详细介绍如何使用该API&…...

护眼-科学使用显示器

一 显示色温对眼睛的影响 显示器的色温设置对护眼效果至关重要&#xff0c;合适的色温可减少蓝光伤害并缓解视疲劳。最护眼的色温并非固定值&#xff0c;需根据环境光、使用时间和场景动态调整。白天推荐6500K左右&#xff0c;夜晚降至3000K-4000K&#xff0c;并借助自动调节工…...

HarmonyOS:1.7

判断题 1.订阅网络状态变化事件时&#xff0c;通过NetConnection类型的对象调用on方法&#xff0c;传入具体事件类型即可&#xff1a; 错误(False) 2.若使用HTTP发起一个GET请求&#xff0c;直接调用get方法&#xff0c;传入请求资源的URL&#xff0c;即可发起请求&#xff…...

物联网赋能玻璃制造业:实现设备智能管理与生产协同

在当今数字化时代&#xff0c;物联网技术正深刻改变着传统制造业的发展模式&#xff0c;玻璃制造业也不例外。物联网的赋能&#xff0c;为玻璃制造业带来了设备智能管理与生产协同的新机遇&#xff0c;推动其向智能化、高效化迈进。 在设备智能管理方面&#xff0c;物联网通过…...

【我的创作纪念日】 --- 与CSDN走过的第365天

个人主页&#xff1a;夜晚中的人海 不积跬步&#xff0c;无以至千里&#xff1b;不积小流&#xff0c;无以成江海。-《荀子》 文章目录 &#x1f389;一、机缘&#x1f680;二、收获&#x1f3a1;三、 日常⭐四、成就&#x1f3e0;五、憧憬 &#x1f389;一、机缘 光阴似箭&am…...

路由器转发规则设置方法步骤,内网服务器端口怎么让异地连接访问的实现

在路由器上设置端口转发&#xff08;Port Forwarding&#xff09;可以将外部网络流量引导到特定的局域网设备&#xff0c;这对于需要远程访问服务器、摄像头、游戏主机等设备非常有用。 登录路由器管理界面&#xff0c;添加端口转发规则让外网访问内网的实现教程分享。以下是设…...

Kotlin 的 suspend 关键字

更多相关知识 Kotlin 的 suspend 关键字是 Kotlin 协程的核心组成部分&#xff0c;它用于标记一个函数可以被挂起&#xff08;暂停执行&#xff09;并在稍后恢复执行&#xff0c;而不会阻塞线程。 理解 suspend 的作用需要从以下几个方面入手&#xff1a; 1. 允许非阻塞的异步…...

Java面试实战:从Spring Boot到微服务的深入探讨

Java面试实战&#xff1a;从Spring Boot到微服务的深入探讨 场景&#xff1a;电商场景的面试之旅 在某互联网大厂的面试间&#xff0c;面试官李老师正襟危坐&#xff0c;而对面坐着的是传说中的“水货程序员”赵大宝。 第一轮&#xff1a;核心Java与构建工具 面试官&#x…...

文件操作和IO(上)

绝对路径和相对路径 文件按照层级结构进行组织&#xff08;类似于数据结构中的树型结构&#xff09;&#xff0c;将专门用来存放管理信息的特殊文件称为文件夹或目录。对于文件系统中文件的定位有两种方式&#xff0c;一种是绝对路径&#xff0c;另一种是相对路径。 绝对路径…...

【Dify(v1.2) 核心源码深入解析】Apps 模块

重磅推荐专栏&#xff1a; 《大模型AIGC》 《课程大纲》 《知识星球》 本专栏致力于探索和讨论当今最前沿的技术趋势和应用领域&#xff0c;包括但不限于ChatGPT和Stable Diffusion等。我们将深入研究大型模型的开发和应用&#xff0c;以及与之相关的人工智能生成内容&#xff…...

小测验——根据调整好的参数进行批量输出

文章目录 一、前言与目的二、思考坐标系怎么生成2.1 补2.2 对于自己投影代码中对数据集参数的情况(取负)总结三、代码2.1 用这套代码可视化 pytorch3d能跑通的例子2.2 gshell的例子2.3 直接手写投影的例子四、思路4.1 确定牛和衣服方向4.2 推测牛的视角4.3 教程学习4.3.1 fov…...

蓝耘平台介绍:算力赋能AI创新的智算云平台

一、蓝耘平台是什么 蓝耘智算云&#xff08;LY Cloud&#xff09;是蓝耘科技打造的现代化GPU算力云服务平台&#xff0c;深度整合自研DS满血版大模型技术与分布式算力调度能力&#xff0c;形成"模型算力"双轮驱动的技术生态。平台核心优势如下&#xff1a; 平台定位…...

23种设计模式-结构型模式之桥接模式(Java版本)

Java 桥接模式&#xff08;Bridge Pattern&#xff09;详解 &#x1f309; 什么是桥接模式&#xff1f; 桥接模式用于将抽象部分与实现部分分离&#xff0c;使它们可以独立变化。 通过在两个独立变化的维度之间建立“桥”&#xff0c;避免因多维度扩展导致的类爆炸。 &#x…...

Python常用的第三方模块之数据分析【pdfplumber库、Numpy库、Pandas库、Matplotlib库】

【pdfplumber库】从PDF文件中读取内容 import pdfplumber #打开PDF文件 with pdfplumber.open(DeepSeek从入门到精通(20250204).pdf) as pdf:for i in pdf.pages: #遍历页print(i.extract_text()) #extract_text()方法提取内容print(f----------------第{i.page_number}页结束…...

PerfettoSQL

​​​​# Device State: Top App # select id, ts, dur, name from (__query_slice_track__long_battery_tracing_Device_State_Top_app) --> 简便方法 """ INCLUDE PERFETTO MODULE android.battery_stats; select * from android_battery_stats_event_s…...

【Python笔记 03 】运算符

一、算数运算符 1、加减乘除 #加法 print (11) #减法 print (1-1) #乘法 print (1*1) #除法&#xff0c;注&#xff1a;商一定是float浮点数&#xff0c;不管是否能整数&#xff0c;且除数不能为0&#xff0c;如下图&#xff1a; print (1/1) 如果除数为0即报错提示。 …...

组网技术-BGP技术,IS-IS协议,VRRP技术

1.BGP在不同自治系统AS进行路由转发 EBGP外部边界网关协议 IBGP内部边界网关协议 2.AS指的是同一个组织管理下&#xff0c;使用统一选路策略的设备集合 3.AS直接需要直连链路&#xff0c;或者通过VPN协议构造逻辑直连进行邻居建立 4.使用IGP可能存在暴露AS内部的网络信息的…...

Word处理控件Spire.Doc系列教程:C# 为 Word 文档设置背景颜色或背景图片

在 Word 文档中&#xff0c;白色是默认的背景设置。一般情况下&#xff0c;简洁的白色背景足以满足绝大多数场景的使用需求。但是&#xff0c;如果您需要创建简历、宣传册或其他创意文档&#xff0c;设置独特的背景颜色或图片能够极大地增强文档的视觉冲击力。本文将演示如何使…...

极狐GitLab 中如何自定义角色?

极狐GitLab 是 GitLab 在中国的发行版&#xff0c;关于中文参考文档和资料有&#xff1a; 极狐GitLab 中文文档极狐GitLab 中文论坛极狐GitLab 官网 自定义角色 (ULTIMATE ALL) 引入于极狐GitLab 15.7&#xff0c;功能标志为 customizable_roles。默认启用于极狐GitLab 15.9…...

JAVA:Web安全防御

目录 一、Web安全基础与常见威胁 OWASP Top 10核心漏洞解析 • SQL注入&#xff08;SQLi&#xff09;、跨站脚本&#xff08;XSS&#xff09;、跨站请求伪造&#xff08;CSRF&#xff09; • 不安全的反序列化、敏感数据泄露 Java后端常见攻击场景 • 通过HttpServletRequest…...

Nginx:支持 HTTPS

文章目录 Nginx 开启 ssl 以支持 HTTPS1 生成本地证书2 开启 ssl 以支持 HTTPS3 将 https 的请求转发给 http 最终的 nginx.conf 如下 Nginx 开启 ssl 以支持 HTTPS [!IMPORTANT] 在下文中&#xff0c;将采用如下定义。 HTTP端口&#xff1a; 80 HTTPS端口&#xff1a; 443 服务…...