本文共 1610 字，大约阅读时间需要 5 分钟。

1、把dist 初始为负无穷

2、松弛判断条件改为 dist[v] < dist[u] + w;

import java.util.ArrayList;import java.util.Scanner;import java.util.Stack;import Graph.HasCycle;import javafx.scene.effect.Light.Distant;public class TopDij {	static boolean[]visit;	static boolean[]onStack;	static Stack
   
     stack;	static int n, m;	static boolean hasCycle = false;	static int[]dis;	static int INF = 99999999;	static ArrayList
    
      []adj;	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		n = in.nextInt();		m = in.nextInt();		visit = new boolean[n+1];		adj = new ArrayList[n+1];		stack = new Stack<>();		dis = new int[n+1];		onStack = new boolean[n+1];		for(int i = 1; i <= n; i++ ) {			adj[i] = new ArrayList<>();		}		for(int i = 0; i < m; i++ ) {			int from = in.nextInt();			int to = in.nextInt();			int w = in.nextInt();			adj[from].add(new EdgeS(from, to, w));		}		bfs(1);		if(!hasCycle) {			shortPath(1);			System.out.println(dis[3]);		}		else {			System.out.println("hasCycle");		}	}	public static void shortPath(int s) {		for(int i = 1; i <= n; i++ ) {			dis[i] = -INF;		}		dis[s] = 0;		while(!stack.isEmpty()) {			int cur = stack.pop();			for(EdgeS e: adj[cur]) {				if(dis[e.to] < dis[cur] + e.w) {					dis[e.to] = dis[cur] + e.w;				}			}		}			}	public static void bfs(int cur) {		visit[cur] = true;		onStack[cur] = true;		for(EdgeS e:adj[cur]) {			if(!visit[e.to]) {				bfs(e.to);			}			else if(onStack[e.to]){				hasCycle = true;				return;			}		}		onStack[cur] = false;		stack.push(cur);	}}class EdgeS{	int from, to, w;	public EdgeS(int f, int t, int w) {		from = f;		to = t;		this.w = w;	}}
    
   

转载地址：http://xlimi.baihongyu.com/