P1807 最長路 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

題目要求我們求出第1號到第n號節(jié)點之間最長的距離。

我們想到使用拓?fù)渑判騺砬笞铋L路。

正常來講，我們應(yīng)該把1號節(jié)點入隊列，再出隊列，把一號節(jié)點能到達(dá)的所有的點的入度減一，并且將這些點求到達(dá)一號節(jié)點的最大距離。如果一個節(jié)點的入度為0，那說明所有與他直接來鏈接的點都跑了一邊，最后最大的也就跑出來了。即使任意兩個點有多條鏈接路徑也不礙事，為什么呢？舉個例子，一號和二號點有三條路徑分別為1，2，3，我們放進(jìn)隊列里后，會先后跑這三段長度最后取得最優(yōu)。但是這道題目有個小坑點，那就是這種情況

這種情況下我們初始時期是只存入了一號節(jié)點所置。

由于3號節(jié)點還有一條入度，而2號節(jié)點我們沒有初始化放入，即使他的入度為0也不能進(jìn)入隊列，所以3號節(jié)點無法到達(dá)，但實際1號節(jié)點可以到達(dá)3號節(jié)點，解決方法就是首先把非1號的所有的入度為0的節(jié)點先入隊列，然后排除干擾，最后就可以按照原步驟進(jìn)行了。

附上代碼

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號節(jié)點開始，來求得所有入讀為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]--;//進(jìn)行值得更改if(rudu[b1.to]==0) {//入度為0那么就加入隊列l(wèi)l1.add(b1.to);}}}
if(dis[aa]==Integer.MIN_VALUE) {System.out.println("-1");
}
else {System.out.println(dis[aa]);
}}public static int aa;//點的總數(shù)public static int bb;//邊的總數(shù)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;}}