벨만포드?

• 출발지로부터 다른 목적지들로 최단 거리를 구할 수 있음

• 다익스트라와 다르게 음수 사이클에 대해서 확인 가능

• 시간복잡도는 O(V * E)

• 거리 배열을 출발지만 0으로 만들어놓고 나머지는 모두 최댓값으로 갱신

• 매 단계에서 모든 간선을 검사하므로, 출발지부터 점차 확장되면서 거리를 갱신하게됨

• 출발지를 제외한 N - 1번 검사를 하게 되고, N번째에도 거리가 줄어든다면 음수 사이클이 존재함을 판단

코드 ?

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static class Edge{
		int s, e;
		long c;
		
		Edge(int s, int e, long c){
			this.s = s;
			this.e = e;
			this.c = c;
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		
		long[] dist = new long[N + 1];
		Arrays.fill(dist, Long.MAX_VALUE);
		List<Edge> list = new ArrayList<>();
		dist[1] = 0;
		
		for(int i = 0; i < M; i++){
			stk = new StringTokenizer(br.readLine());
			
			int A = Integer.parseInt(stk.nextToken());
			int B = Integer.parseInt(stk.nextToken());
			long C = Long.parseLong(stk.nextToken());
			
			list.add(new Edge(A, B, C));
		}
		
		for(int i = 1; i <= N; i++){
			for(Edge edge : list){
				if(dist[edge.s] != Long.MAX_VALUE && 
				dist[edge.e] > dist[edge.s] + edge.c){
					dist[edge.e] = dist[edge.s] + edge.c;
					if(i == N){
						bw.write("-1\n");
						bw.flush();
						return;
					}
				}	
			}
		}
	}
}