拓扑排序求最长路
P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求我们求出第1号到第n号节点之间最长的距离。
我们想到使用拓扑排序来求最长路。
正常来讲,我们应该把1号节点入队列,再出队列,把一号节点能到达的所有的点的入度减一,并且将这些点求到达一号节点的最大距离。如果一个节点的入度为0,那说明所有与他直接来链接的点都跑了一边,最后最大的也就跑出来了。即使任意两个点有多条链接路径也不碍事,为什么呢?举个例子,一号和二号点有三条路径分别为1,2,3,我们放进队列里后,会先后跑这三段长度最后取得最优。但是这道题目有个小坑点,那就是这种情况

这种情况下我们初始时期是只存入了一号节点所置。
由于3号节点还有一条入度,而2号节点我们没有初始化放入,即使他的入度为0也不能进入队列,所以3号节点无法到达,但实际1号节点可以到达3号节点,解决方法就是首先把非1号的所有的入度为0的节点先入队列,然后排除干扰,最后就可以按照原步骤进行了。
附上代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main { public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
bb=Integer.parseInt(aStrings[1]);
al1=new ArrayList[aa+1];
int a;
rudu=new int[aa+1];
for(a=1;a<=aa;a++) {al1[a]=new ArrayList<>();
}
for(a=1;a<=bb;a++) {String[] bStrings=br.readLine().split(" ");int b=Integer.parseInt(bStrings[0]);int c=Integer.parseInt(bStrings[1]);int d=Integer.parseInt(bStrings[2]);al1[b].add(new edge(c, d));//存储边rudu[c]++;//入度加一
}for(a=2;a<=aa;a++) {if(rudu[a]==0) {//为了解决上述问题我们从2号节点开始,来求得所有入读为0的点的序号ll1.add(a);}
}
dis=new int[aa+1];
Arrays.fill(dis, Integer.MIN_VALUE);
dis[1]=0;//初始点到初始点的距离肯定为0
ll1.add(1);//在这里最后加入初始点
while(ll1.size()!=0) {//取出入读为0的点int a1=ll1.remove();for(edge b1:al1[a1]) {dis[b1.to]=Math.max(dis[b1.to], dis[a1]+b1.length);rudu[b1.to]--;//进行值得更改if(rudu[b1.to]==0) {//入度为0那么就加入队列ll1.add(b1.to);}}}
if(dis[aa]==Integer.MIN_VALUE) {System.out.println("-1");
}
else {System.out.println(dis[aa]);
}}public static int aa;//点的总数public static int bb;//边的总数public static ArrayList<edge>[] al1;//存储边的集合public static int[] rudu;//记录每一个点的入度public static LinkedList<Integer> ll1=new LinkedList<>();//记录每一个入度为0的点public static int[] dis;//记录每个点距离初始点的距离。}
class edge{int to;int length;public edge(int to, int length) {super();this.to = to;this.length = length;}}
相关文章:
拓扑排序求最长路
P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目要求我们求出第1号到第n号节点之间最长的距离。 我们想到使用拓扑排序来求最长路。 正常来讲,我们应该把1号节点入队列,再出队列,把一号节点能到达的所有的点的入度减一&a…...
sqli-lab靶场通关
文章目录 less-1less-2less-3less-4less-5less-6less-7less-8less-9less-10 less-1 1、提示输入参数id,且值为数字; 2、判断是否存在注入点 id1报错,说明存在 SQL注入漏洞。 3、判断字符型还是数字型 id1 and 11 --id1 and 12 --id1&quo…...
使用 Apache Camel 和 Quarkus 的微服务(五)
【squids.cn】 全网zui低价RDS,免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 在本系列的第三部分中,我们了解了如何在 Minikube 中部署基于 Quarkus/Camel 的微服务,这是最常用的 Kubernetes 本地实现之一。虽然这样的本地…...
Ubuntu磁盘满了,导致黑屏
前言 (1)最近要玩Milk-V Duo,配置环境过程中,发现磁盘小了。于是退出虚拟机,扩大Ubuntu大小,重新开机,发现无法进入Ubuntu界面。 (2)查了很久,后面发现是磁盘…...
安装sklearn包错误解决以及 scikit-learn简介
安装sklearn包错误解决以及 scikit-learn简介 利用 pip install sklearn时出现错误 pip install sklearn Looking in indexes: https://mirrors.aliyun.com/pypi/simple/ Collecting sklearnUsing cached https://mirrors.aliyun.com/pypi/packages/b9/0e/b2a4cfaa9e12b9ca4…...
CSS点击切换或隐藏盒子的卷起、展开效果
<template><div class"main"><el-button click"onCllick">切换</el-button><transition name"slideDown"><div class"info" v-if"isShow">1111</div></transition></di…...
关于信息安全软考的一些记录1
1、网络信息安全的基本属性 机密性:网络信息不泄露给非授权的用户完整性:未经授权必能改的特性可用性:可以及时获取网络信息和服务的特性可控性:责任主体对网络信息系统具有管理、支配的能力【可管理、可支配】扛抵赖性ÿ…...
如何选择UMLChina服务
服务口号:聚焦最后一公里 斐力庇第斯从马拉松跑回雅典报信,虽然已是满身血迹、精疲力尽,但他知道:没有出现在雅典人民面前,前面的路程都是白费。 学到的知识如果不能最终【用】于您自己的项目之中,也同样是…...
关于信息安全软考的记录3
1、网络安全体系的特征 网络安全体系:网络安全保障系统的最高层概念抽象 特征内容整体性网络安全单元按照一定的规则,相互依赖、相互作用而形成人机物一体化的网络安全保护方式协同性通过各种安全机制的相互协作,构建系统性的网络安全保护方…...
API攻防-接口安全SOAPOpenAPIRESTful分类特征导入项目联动检测
文章目录 概述什么是接口? 1、API分类特征SOAP - WSDLWeb services 三种基本元素: OpenApi - Swagger UISpringboot Actuator 2、API检测流程Method:请求方法URL:唯一资源定位符Params:请求参数Authorizationÿ…...
【Docker 内核详解】namespace 资源隔离(二):UTS namespace IPC namespace
namespace 资源隔离(二):UTS namespace & IPC namespace 1.UTS namespace UTS(UNIX Time-sharing System),UTS namespace 提供了 主机名 和 域名 的隔离,这样每个 Docker 容器就可以拥有独…...
EOF() | BOF()相关题目解析
题目 设当前数据库有10条记录(记录未进行任何索引),在下列3种情况下,当前记录号为1时:EOF()为真时;BOF()为真时,命令RECN()的结果分别是______。 A.1,11,1B.1,10,1C.1,11,0D…...
spring 注入 当有两个参数的时候 接上面
新加一个int 型的 age 记得写getset方法和构造方法 ((((((( 构造方法的作用——无论是有参构造还是无参构造,他的作用都是为了方便为对象的属性初始化值 构造方法是一种特殊的方…...
博客文档续更
十、 博客前台模块-异常处理 目前我们的项目在认证出错或者权限不足的时候响应回来的Json,默认是使用Security官方提供的响应的格式,但是这种响应的格式肯定是不符合我们项目的接口规范的。所以需要自定义异常处理 我们需要去实现AuthenticationEntryP…...
OCR让点读笔如虎添翼
点读笔是一种智能学习工具,它可以通过识别文字来提供相应的语音或图像反馈。在实现文字识别功能时,点读笔通常会借助OCR(Optical Character Recognition,光学字符识别)技术。下面将详细介绍点读笔如何利用OCR技术实现文…...
棱镜七彩参编!开源领域4项团体标准正式发布
近日,中电标2023年第27号团体标准公告正式发布,《T/CESA 1270.2-2023 信息技术 开源治理 第 2 部分:企业治理评估模型》、《T/CESA 1270.3-2023 信息技术 开源治理 第 3 部分:社区治理框架》、《T/CESA 1270.5-2023 信息技术 开源…...
轻量级Composition
MEF,全称Managed Extensibility Framework(托管可扩展框架)。MEF是专门致力于解决扩展性问题的框架。MEF 位于 ComponentModel.Composition 程序集中,添加 System.ComponentModel.Composition 和 System.ComponentModel.Compositi…...
Vxlan网络和flannel记录
Vxlan 大二层网络,在三层网络中构建逻辑的2层网络 数据包经过vxlan隧道 用vni标识不同的vxlan网络(类似于vlan的vid) 通过vtep来封装和解封装,通过UDP传输 Flannel 分配子网和IP地址:Flannel为每个容器或虚拟机分配唯一…...
【已解决】微信小程序-苹果手机日期解析异常
在开发微信小程序时,使用了 uView 的 CountDown倒计时 组件和 uni.$u.timeFrom Api,后台传递了一个时间字符串,前台计算时间戳的差值,来显示还有多久开始,这个功能在模拟器和我自己手机(iphon13)…...
Avalonia如何更改全局背景色
1.项目下载地址:https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia,项目地址 https://github.com/irihitech/Semi.Avalonia 3.ColorView,使用Semi.Avalonia.ColorPicker,Nuget获取就行 4.样式预览 以下是…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
