[백준 1865] 웜홀(Java)

문제 링크 : https://www.acmicpc.net/problem/1865

이 문제는 벨만 포드 알고리즘을 이용하여 풀 수 있습니다. 문제에서 구하고자 하는 사이클은 음수 사이클을 판별하는 문제이기 때문에 벨만 포드 알고리즘을 사용합니다. 하지만 여기서 주의할 점은 일차원 배열로 구성된 간선 리스트가 아닌 인접 리스트로 입력이 주어지기 때문에 최단 거리 배열값이 충분히 큰 수일 경우에만 최솟값을 대입하는 것이 아니라 모든 방문하는 노드의 간선들을 모두 연결해주어야 합니다.

다음은 코드입니다.

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

class Main{
    static int T,N,M,W;
    static List<Edge> graph;
    static long[] distance;

    public static void main(String[] args) throws Exception{
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-- >0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            graph = new ArrayList<>();

            for(int i=0;i<M+W;i++){
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                if(i<M){
                    graph.add(new Edge(s,e,v));
                    graph.add(new Edge(e,s,v));
                }
                else graph.add(new Edge(s,e,-v));
            }

            distance = new long[N+1];
            Arrays.fill(distance,Integer.MAX_VALUE);
            distance[1] = 0;

            for(int i=1;i<=N;i++){
                for(int j=0;j<graph.size();j++){
                    Edge edge = graph.get(j);

//                    if(distance[edge.s] != Integer.MAX_VALUE)
                        distance[edge.e] = Math.min(distance[edge.e], distance[edge.s]+ edge.v);
                }
            }

            boolean minusCycle = false;
            for(int i=0;i< graph.size();i++){
                Edge edge = graph.get(i);
//                if(distance[edge.s] != Integer.MAX_VALUE && distance[edge.e] > distance[edge.s]+ edge.v){
                if(distance[edge.e] > distance[edge.s]+ edge.v){
                    minusCycle = true;
                    break;
                }
            }

            if(minusCycle) sb.append("YES\n");
            else sb.append("NO\n");
        }
        System.out.println(sb);
    }

    static class Edge{
        int s;
        int e;
        int v;

        Edge(int s, int e, int v){
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }
}