bellman-ford(java)

参考代码:

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		int[] dist = new int[n];
		List<int[]> edges = new ArrayList<>();
		for(int i = 0; i < n; i++) {
		    dist[i] = (int) 1e9;
		}
		dist[0] = 0;
		for(int i = 0; i < n; i++) {
		    for(int j = 0; j < n; j++) {
		        int z = cin.nextInt();
		        if(i != j && z != 0) edges.add(new int[]{i, j, z});
		    }
		}
		for(int i = 1; i <= n - 1; i++) {
		    boolean flag = false;
		    for(int[] edge : edges) {
    		    int x = edge[0];
    		    int y = edge[1];
    		    int z = edge[2];
    		    if(dist[x] + z < dist[y]) {
    		        dist[y] = dist[x] + z;
    		        flag = true;
    		    }
    		}
    		if(!flag) break;
		}
		System.out.print(dist[n - 1]);
		
		
		
	}
}