拓扑排序求最长路

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[] al1;//存储边的集合
	public static int[] rudu;//记录每一个点的入度
	public static LinkedList 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;
	}
	
}