购物网站制作公司,搜狗优化好的网站,网站软文推广好处,昆明小程序制作P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求我们求出第1号到第n号节点之间最长的距离。
我们想到使用拓扑排序来求最长路。
正常来讲#xff0c;我们应该把1号节点入队列#xff0c;再出队列#xff0c;把一号节点能到达的所有的点的入度减一我们应该把1号节点入队列再出队列把一号节点能到达的所有的点的入度减一并且将这些点求到达一号节点的最大距离。如果一个节点的入度为0那说明所有与他直接来链接的点都跑了一边最后最大的也就跑出来了。即使任意两个点有多条链接路径也不碍事为什么呢举个例子一号和二号点有三条路径分别为123我们放进队列里后会先后跑这三段长度最后取得最优。但是这道题目有个小坑点那就是这种情况 这种情况下我们初始时期是只存入了一号节点所置。
由于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 scnew Scanner(System.in);
BufferedReader brnew BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1new PrintWriter(System.out);
String[] aStringsbr.readLine().split( );
aaInteger.parseInt(aStrings[0]);
bbInteger.parseInt(aStrings[1]);
al1new ArrayList[aa1];
int a;
rudunew int[aa1];
for(a1;aaa;a) {al1[a]new ArrayList();
}
for(a1;abb;a) {String[] bStringsbr.readLine().split( );int bInteger.parseInt(bStrings[0]);int cInteger.parseInt(bStrings[1]);int dInteger.parseInt(bStrings[2]);al1[b].add(new edge(c, d));//存储边rudu[c];//入度加一
}for(a2;aaa;a) {if(rudu[a]0) {//为了解决上述问题我们从2号节点开始来求得所有入读为0的点的序号ll1.add(a);}
}
disnew int[aa1];
Arrays.fill(dis, Integer.MIN_VALUE);
dis[1]0;//初始点到初始点的距离肯定为0
ll1.add(1);//在这里最后加入初始点
while(ll1.size()!0) {//取出入读为0的点int a1ll1.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 ArrayListedge[] al1;//存储边的集合public static int[] rudu;//记录每一个点的入度public static LinkedListInteger ll1new 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;}}
