[JAVA] 백준 1865 - 웜홀

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

특정 정점에서 출발해서 다시 해당 정점으로 돌아왔을 때, 가중치가 음수값인 정점의 존재 여부를 구하는 문제이다.

 그리디 기반인 다익스트라는 음수 가중치에서 사용하지 못하고  출발점이 명시되지 않았으므로 모든 정점을 염두에 두어야해서 플로이드 워셜을 선택했다.

도로는 양방향으로 입력했고, 웜홀은 단방향으로 입력했다.

동일 노선에 여러 경로가 있을 수 있으므로 최소값만 저장하도록 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int tc = Integer.parseInt(s);
        for (int i = 0; i < tc; i++) {
            int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int[][] map = new int[a[0]][a[0]];
            for (int j = 0; j < a[0]; j++) {
                Arrays.fill(map[j],99999999);
                map[j][j] = 0;
            }
            for (int j = 0; j < a[1]; j++) {
                int[] b = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                map[b[0]-1][b[1]-1] = Math.min(b[2], map[b[0]-1][b[1]-1]);
                map[b[1]-1][b[0]-1] = Math.min(b[2], map[b[1]-1][b[0]-1]);
            }
            for (int j = 0; j < a[2]; j++) {
                int[] b = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                map[b[0]-1][b[1]-1] = Math.min(b[2]*-1,map[b[0]-1][b[1]-1]);
            }
            for (int k = 0; k < a[0]; k++) {
                for (int j = 0; j < a[0]; j++) {
                    for (int l = 0; l < a[0]; l++) {
                        if(map[j][k]+map[k][l]<map[j][l]){
                            map[j][l] = map[j][k]+map[k][l];
                        }
                    }
                }
            }
            boolean flag = false;
            for (int j = 0; j < a[0]; j++) {
                if(map[j][j]<0){
                    flag = true;
                    break;
                }
            }
            if(flag) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}