[BOJ_1865] 웜홀

설명

---

웜홀 문제는 벨만 포드 알고리즘을 활용한 문제입니다. 누락된 조건 중 모든 그래프가 연결 그래프가 아닐 수 있음을 판단하고 문제를 풀어야 합니다. 그리고, 도로는 양방향이고 웜홀은 단방향임을 명심해야합니다. 그래서, 문제를 풀게 되면 아래와 같은 형태로 작성 할 수 있습니다. 

 

그리고, 음수 사이클이 생기면 시간이 줄어들면서 원래 제자리로 돌아오는 것이니 음수 사이클 여부를 체크하면 됩니다.

 

코드

---

package BOJ.shortest_path;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_1865 {
    static class Edge{
        int from;
        int to;
        int weight;
        public Edge(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    static int N,M,W;
    static List<Edge> graph;
    static long[] minDist;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int T = Integer.parseInt(tk.nextToken());

        while (T-- > 0){
            tk = new StringTokenizer(in.readLine()," ");
            N = Integer.parseInt(tk.nextToken());
            M = Integer.parseInt(tk.nextToken());
            W = Integer.parseInt(tk.nextToken());
            minDist = new long[N + 1];
            Arrays.fill(minDist, 100_000_000);
            graph = new ArrayList<Edge>();

            for (int i = 0; i < M; i++){
                tk = new StringTokenizer(in.readLine()," ");
                int S = Integer.parseInt(tk.nextToken());
                int E = Integer.parseInt(tk.nextToken());
                int D = Integer.parseInt(tk.nextToken());
                graph.add(new Edge(S,E,D));
                graph.add(new Edge(E,S,D));

            }

            for (int i = 0; i < W; i++){
                tk = new StringTokenizer(in.readLine()," ");
                int S = Integer.parseInt(tk.nextToken());
                int E = Integer.parseInt(tk.nextToken());
                int D = Integer.parseInt("-" + tk.nextToken());
                graph.add(new Edge(S,E,D));
            }

            if(belmanFord()){
                System.out.println("NO");
            }else{
                System.out.println("YES");
            }
        }
    }

    private static boolean belmanFord() {
        minDist[1] = 0;
        for (int i = 0; i < N - 1 + M; i++){
            for (Edge edge : graph){
                if(minDist[edge.to] > minDist[edge.from] + edge.weight){
                    minDist[edge.to] = minDist[edge.from] + edge.weight;
                }
            }
        }

        for (Edge edge : graph){
            if(minDist[edge.to] > minDist[edge.from] + edge.weight){
                return false;
            }
        }
        return true;
    }
}

 

1865번: 웜홀