NineTwo meet you

벨만 포드 (Bellman-Ford) 단일 시작점 최단 경로 알고리즘 음수 간선 포함 가능 동작 과정 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다. 최단 경로는 최대 V개의 정점을 갖기 때문에 잘해야 V-1개의 간선을 가질 수 있다. 따라서 모든 간선에 대한 완화 과정은 V-1번이면 충분하다. 음수 사이클 판정 완화를 V번 시도하면 된다. 음수 사이클이 존재하지 않다면 V-1번이면 최단 거리를 찾아낼 수 있다. 만일 V번째 완화 과정에서 한번더 완화가 성공한다면 이는 음수 사이클이 존재한다고 생각할 수 있게 된다. static int n; // 정점의 개수 static int m; // 간선의 개수 static ArrayList[] al = new ArrayList[n+1]; // 그래프의..