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

拓扑排序求最长路

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号节点之间最长的距离。 我们想到使用拓扑排序来求最长路。 正常来讲&#xff0c;我们应该把1号节点入队列&#xff0c;再出队列&#xff0c;把一号节点能到达的所有的点的入度减一&a…...

sqli-lab靶场通关

文章目录 less-1less-2less-3less-4less-5less-6less-7less-8less-9less-10 less-1 1、提示输入参数id&#xff0c;且值为数字&#xff1b; 2、判断是否存在注入点 id1报错&#xff0c;说明存在 SQL注入漏洞。 3、判断字符型还是数字型 id1 and 11 --id1 and 12 --id1&quo…...

使用 Apache Camel 和 Quarkus 的微服务(五)

【squids.cn】 全网zui低价RDS&#xff0c;免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 在本系列的第三部分中&#xff0c;我们了解了如何在 Minikube 中部署基于 Quarkus/Camel 的微服务&#xff0c;这是最常用的 Kubernetes 本地实现之一。虽然这样的本地…...

Ubuntu磁盘满了,导致黑屏

前言 &#xff08;1&#xff09;最近要玩Milk-V Duo&#xff0c;配置环境过程中&#xff0c;发现磁盘小了。于是退出虚拟机&#xff0c;扩大Ubuntu大小&#xff0c;重新开机&#xff0c;发现无法进入Ubuntu界面。 &#xff08;2&#xff09;查了很久&#xff0c;后面发现是磁盘…...

安装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、网络信息安全的基本属性 机密性&#xff1a;网络信息不泄露给非授权的用户完整性&#xff1a;未经授权必能改的特性可用性&#xff1a;可以及时获取网络信息和服务的特性可控性&#xff1a;责任主体对网络信息系统具有管理、支配的能力【可管理、可支配】扛抵赖性&#xff…...

如何选择UMLChina服务

服务口号&#xff1a;聚焦最后一公里 斐力庇第斯从马拉松跑回雅典报信&#xff0c;虽然已是满身血迹、精疲力尽&#xff0c;但他知道&#xff1a;没有出现在雅典人民面前&#xff0c;前面的路程都是白费。 学到的知识如果不能最终【用】于您自己的项目之中&#xff0c;也同样是…...

关于信息安全软考的记录3

1、网络安全体系的特征 网络安全体系&#xff1a;网络安全保障系统的最高层概念抽象 特征内容整体性网络安全单元按照一定的规则&#xff0c;相互依赖、相互作用而形成人机物一体化的网络安全保护方式协同性通过各种安全机制的相互协作&#xff0c;构建系统性的网络安全保护方…...

API攻防-接口安全SOAPOpenAPIRESTful分类特征导入项目联动检测

文章目录 概述什么是接口&#xff1f; 1、API分类特征SOAP - WSDLWeb services 三种基本元素&#xff1a; OpenApi - Swagger UISpringboot Actuator 2、API检测流程Method&#xff1a;请求方法URL&#xff1a;唯一资源定位符Params&#xff1a;请求参数Authorization&#xff…...

【Docker 内核详解】namespace 资源隔离(二):UTS namespace IPC namespace

namespace 资源隔离&#xff08;二&#xff09;&#xff1a;UTS namespace & IPC namespace 1.UTS namespace UTS&#xff08;UNIX Time-sharing System&#xff09;&#xff0c;UTS namespace 提供了 主机名 和 域名 的隔离&#xff0c;这样每个 Docker 容器就可以拥有独…...

EOF() | BOF()相关题目解析

题目 设当前数据库有10条记录(记录未进行任何索引)&#xff0c;在下列3种情况下&#xff0c;当前记录号为1时&#xff1a;EOF()为真时&#xff1b;BOF()为真时&#xff0c;命令RECN()的结果分别是______。 A&#xff0e;1,11,1B&#xff0e;1,10,1C&#xff0e;1,11,0D&#xf…...

spring 注入 当有两个参数的时候 接上面

新加一个int 型的 age 记得写getset方法和构造方法 &#xff08;&#xff08;&#xff08;&#xff08;&#xff08;&#xff08;&#xff08; 构造方法的作用——无论是有参构造还是无参构造&#xff0c;他的作用都是为了方便为对象的属性初始化值 构造方法是一种特殊的方…...

博客文档续更

十、 博客前台模块-异常处理 目前我们的项目在认证出错或者权限不足的时候响应回来的Json&#xff0c;默认是使用Security官方提供的响应的格式&#xff0c;但是这种响应的格式肯定是不符合我们项目的接口规范的。所以需要自定义异常处理 我们需要去实现AuthenticationEntryP…...

OCR让点读笔如虎添翼

点读笔是一种智能学习工具&#xff0c;它可以通过识别文字来提供相应的语音或图像反馈。在实现文字识别功能时&#xff0c;点读笔通常会借助OCR&#xff08;Optical Character Recognition&#xff0c;光学字符识别&#xff09;技术。下面将详细介绍点读笔如何利用OCR技术实现文…...

棱镜七彩参编!开源领域4项团体标准正式发布

近日&#xff0c;中电标2023年第27号团体标准公告正式发布&#xff0c;《T/CESA 1270.2-2023 信息技术 开源治理 第 2 部分&#xff1a;企业治理评估模型》、《T/CESA 1270.3-2023 信息技术 开源治理 第 3 部分&#xff1a;社区治理框架》、《T/CESA 1270.5-2023 信息技术 开源…...

轻量级Composition

MEF&#xff0c;全称Managed Extensibility Framework&#xff08;托管可扩展框架&#xff09;。MEF是专门致力于解决扩展性问题的框架。MEF 位于 ComponentModel.Composition 程序集中&#xff0c;添加 System.ComponentModel.Composition 和 System.ComponentModel.Compositi…...

Vxlan网络和flannel记录

Vxlan 大二层网络&#xff0c;在三层网络中构建逻辑的2层网络 数据包经过vxlan隧道 用vni标识不同的vxlan网络&#xff08;类似于vlan的vid&#xff09; 通过vtep来封装和解封装&#xff0c;通过UDP传输 Flannel 分配子网和IP地址&#xff1a;Flannel为每个容器或虚拟机分配唯一…...

【已解决】微信小程序-苹果手机日期解析异常

在开发微信小程序时&#xff0c;使用了 uView 的 CountDown倒计时 组件和 uni.$u.timeFrom Api&#xff0c;后台传递了一个时间字符串&#xff0c;前台计算时间戳的差值&#xff0c;来显示还有多久开始&#xff0c;这个功能在模拟器和我自己手机&#xff08;iphon13&#xff09…...

Avalonia如何更改全局背景色

1.项目下载地址&#xff1a;https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia&#xff0c;项目地址 https://github.com/irihitech/Semi.Avalonia 3.ColorView&#xff0c;使用Semi.Avalonia.ColorPicker&#xff0c;Nuget获取就行 4.样式预览 以下是…...

寻音捉影·侠客行企业实操案例:法务取证场景下千条采访音频线索挖掘

寻音捉影侠客行企业实操案例&#xff1a;法务取证场景下千条采访音频线索挖掘 1. 引言&#xff1a;音频线索挖掘的法务挑战 在法律取证工作中&#xff0c;经常需要处理大量的采访录音。想象一下这样的场景&#xff1a;一个商业纠纷案件&#xff0c;涉及数十个当事人的访谈录音…...

C语言入门避坑指南:从雨课堂高频错题解析编程新手常见误区

C语言入门避坑指南&#xff1a;从雨课堂高频错题解析编程新手常见误区 刚接触C语言时&#xff0c;很多同学会被看似简单的语法规则绊倒。那些在课堂上反复强调的细节&#xff0c;往往成为考试中最容易丢分的陷阱。本文将结合电子科技大学《程序设计与算法基础I》课程的真实错题…...

Unity 实现Slot Machine两种动态停止效果的实战解析

1. 老虎机效果设计核心思路 老虎机作为经典游戏机制&#xff0c;其动态停止效果直接影响玩家的游戏体验。在Unity中实现这类效果时&#xff0c;我们需要考虑两个关键因素&#xff1a;物理真实感和心理预期管理。缓慢减速效果通过逐渐降低转速营造紧张氛围&#xff0c;而惯性回弹…...

突破Windows限制:告别模拟器烦恼的安卓应用高效工具

突破Windows限制&#xff1a;告别模拟器烦恼的安卓应用高效工具 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 在数字化办公与娱乐融合的今天&#xff0c;Windows用户…...

MMSkeleton部署指南:从开发环境到生产环境的完整迁移

MMSkeleton部署指南&#xff1a;从开发环境到生产环境的完整迁移 【免费下载链接】mmskeleton A OpenMMLAB toolbox for human pose estimation, skeleton-based action recognition, and action synthesis. 项目地址: https://gitcode.com/gh_mirrors/mm/mmskeleton MM…...

别只刷题了!用Python/C++搞定考研机试高频算法(附PIPIOJ真题代码重构与优化)

从暴力解法到优雅实现&#xff1a;Python/C双语言拆解考研机试高频算法 考研机试不仅考察算法理解&#xff0c;更检验工程化编码能力。许多考生能写出正确但冗长的代码&#xff0c;却在时间优化和代码简洁性上失分。本文将用Python和C对比实现六大高频题型&#xff0c;重点分析…...

uni-app Android应用华为审核隐私权限提示与上架授权说明实战指南

1. uni-app Android应用华为审核隐私权限问题解析 第一次用uni-app开发Android应用准备上架华为市场时&#xff0c;我被审核驳回的理由整懵了——"缺少权限使用说明"。明明iOS版本在manifest.json配得好好的&#xff0c;怎么到Android就出问题&#xff1f;后来才发现…...

2026上海紧固件专业展观察:12.9级螺栓为何成为高端制造核心紧固方案?

2026第十六届上海紧固件专业展&#xff08;Fastener Expo Shanghai 2026&#xff09;将于6月24日至26日在上海国家会展中心举办。作为紧固件行业的重要展示窗口&#xff0c;本届展会将集中呈现高强度紧固件的发展趋势&#xff0c;其中12.9级螺栓已成为当前制造业升级的重要标志…...

手把手教你玩转双闭环MMC逆变仿真

双闭环&#xff0b;最近电平逼近调制MMC模块化多电平换流器仿真&#xff08;逆变侧&#xff09;含技术文档 MMC Matlab-Simulink 直流侧11kV 交流侧6.6kV N22 采用最近电平逼近调制NLM 环流抑制&#xff08;PIR比例积分准谐振控制&#xff09;&#xff0c;测量桥臂电感THD获得抑…...

3个高效Searchkit高亮技巧:让你的搜索结果直观又专业

3个高效Searchkit高亮技巧&#xff1a;让你的搜索结果直观又专业 【免费下载链接】searchkit Search UI for Elasticsearch & Opensearch. Compatible with Algolias Instantsearch and Autocomplete components. React & Vue support 项目地址: https://gitcode.com…...