[백준]1865번 웜홀

문제 설명

• https://www.acmicpc.net/problem/1865
• Gold 3

문제 풀이

• 플로이드 워셜 알고리즘으로 모든 노드간의 최소 거리를 구해주었다.
• 결과는 map[i][i] < 0 인 노드가 있으면 분기해서 출력해주었다.

소스 코드 (JAVA)

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    static int T, N, M, W;
    static int[][] map;

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T ; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            map = new int[N+1][N+1];
            for (int i = 1; i <= N; i++) {
                Arrays.fill(map[i], 987654321);
                map[i][i] = 0;
            }
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                if (map[a][b] > c) map[a][b] = c;
                if (map[b][a] > c) map[b][a] = c;
            }
            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                map[a][b] = -c;
            }

            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    for (int k = 1; k <= N; k++) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }

            //결과 출력
            boolean flag = false;
            for (int i = 1; i <= N; i++) {
                if (map[i][i] < 0) {
                    flag = true;
                    break;
                }
            }
            bw.write(flag ? "YES\n" : "NO\n");
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 웜홀 (13:34)
 *
 * - T : 테스트 개수 ( T <= 5)
 * - N : 노드 개수  ( N <= 500)
 * - M : 간선 개수 (방향 X) (M <= 2500)
 * - W : 웜홀 개수 (방향 O) -> 시간이 뒤로감 (W <= 200)
 *
 * - 시작 위치에서 다시 시작 위치로 갔을 떄 시간이 뒤로 가는 경우가 있는지 확인
 *
 * T
 * N M W
 * (M개줄)
 * a b c
 * (W개줄)
 * a b c
 */