[BOJ] 1865번 : 웜홀

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

 

알고리즘 분류

• 그래프 이론
• 벨만-포드

 

문제 파악

위의 캡처에서 알 수 있듯이 "시간이 뒤로 가게 된다"라는 문구로 유추해보면 음수 가중치가 존재한다는 것을 알 수 있고 벨만-포드 알고리즘을 활용하여 문제를 풀어야겠다고 접근했다.

 

추가로 다익스트라, 벨만-포드 알고리즘 중에서 왜 벨만-포드를 선택해야 하는지 궁금했는데 아래 링크에 잘 설명이 되어있어 참조 링크를 달아놓는다.

 

https://hy38.github.io/why-dijkstra-fail-on-a-negative-weighted-edge

다익스트라 알고리즘에서 음수 간선이 존재하면 안되는 이유 - Reason Why Dijkstra Fail on a Negative Weigh

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static final int INF = Integer.MAX_VALUE/10;
    static ArrayList<Edge> edge;
    static int[] dist;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));

        int TC = Integer.parseInt(br.readLine());


        while(TC-->0)
        {

            String[] firstLine = br.readLine().split(" ");

            int N = Integer.parseInt(firstLine[0]);
            int M = Integer.parseInt(firstLine[1]);
            int W = Integer.parseInt(firstLine[2]);


            edge = new ArrayList<>();
            dist = new int[N+1];
            Arrays.fill(dist,INF);

            for(int idx =1; idx<=M;idx++)
            {
                String[] input = br.readLine().split(" ");

                int S = Integer.parseInt(input[0]);
                int E = Integer.parseInt(input[1]);
                int T = Integer.parseInt(input[2]);

                //무방향 그래프 이니까 시작점=>도착점 // 도착점=>시작점으로 추가
                edge.add(new Edge(S,E,T));
                edge.add(new Edge(E,S,T));
            }

            for(int idx = 1; idx<=W;idx++)
            {
                String[] input = br.readLine().split(" ");

                int S = Integer.parseInt(input[0]);
                int E = Integer.parseInt(input[1]);
                int T = Integer.parseInt(input[2]) * -1;
                //웜홀은 유방향
                edge.add(new Edge(S,E,T));
            }

            for(int j=1;j<=N;j++)
            {
                for(Edge e : edge){
                    dist[e.e] = Math.min(dist[e.e],(dist[e.s] + e.t));
                }
            }

            boolean answer = false;
            for(Edge e : edge){
                if(dist[e.e] > dist[e.s] + e.t){
                    answer = true;
                    break;
                }
            }

            if(answer){
                bw.write("YES");
            }else{
                bw.write("NO");
            }
            bw.newLine();
        }
        bw.flush();
        br.close();
    }
    private static class Edge
    {
        int s;
        int e;
        int t;
        public Edge(int s, int e, int t){
            this.s = s;
            this.e = e;
            this.t = t;
        }
    }
}