import java.io.*; import java.util.*; public class Main { private static StringTokenizer st; private static StringBuilder answerString = new StringBuilder(); private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static int T, N, M, W; private static List connInfo; private static int[] parent; private static List> groupNodes; public static void main(String[] args) throws IOException { T = Integer.parseInt(br.readLine()); for (int i = 0; i < T; i++) { inputSetting(); solution(); } System.out.println(answerString); } private static void solution() { // 그룹 분류 makeGroups(); boolean hasCycle = false; boolean[] groupVisited = new boolean[N + 1]; for (int i = 1; i <= N; i++) { int groupId = find(i); if (!groupVisited[groupId]) { if (bellmanFordGroup(groupId)) { hasCycle = true; break; } groupVisited[groupId] = true; } } answerString.append(hasCycle ? "YES\n" : "NO\n"); } // 각 그룹의 노드리스트 생성 private static void makeGroups() { groupNodes = new ArrayList<>(); for (int i = 0; i <= N; i++) groupNodes.add(new ArrayList<>()); for (int i = 1; i <= N; i++) { groupNodes.get(find(i)).add(i); } } // 그룹별 벨만포드 실행 private static boolean bellmanFordGroup(int groupId) { int[] dist = new int[N + 1]; Arrays.fill(dist, Integer.MAX_VALUE); // 해당 그룹의 임의 노드를 시작점으로 List nodes = groupNodes.get(groupId); if (nodes.isEmpty()) return false; dist[nodes.get(0)] = 0; // 벨만포드 for (int iter = 0; iter < nodes.size() - 1; iter++) { for (int[] edge : connInfo) { int from = edge[0]; int to = edge[1]; int val = edge[2]; if (find(from) == groupId && dist[from] != Integer.MAX_VALUE) { if (dist[to] > dist[from] + val) { dist[to] = dist[from] + val; } } } } // 음수 사이클 판별 for (int[] edge : connInfo) { int from = edge[0]; int to = edge[1]; int val = edge[2]; if (find(from) == groupId && dist[from] != Integer.MAX_VALUE) { if (dist[to] > dist[from] + val) { return true; } } } return false; } // 유니온 파인드 기본 로직 private static void union(int a, int b) { a = find(a); b = find(b); if (a != b) parent[b] = a; } private static int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } private static void inputSetting() throws IOException { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); W = Integer.parseInt(st.nextToken()); connInfo = new ArrayList<>(); parent = new int[N + 1]; for (int i = 1; i <= N; i++) parent[i] = i; // 양방향 간선 for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int val = Integer.parseInt(st.nextToken()); connInfo.add(new int[]{from, to, val}); connInfo.add(new int[]{to, from, val}); union(from, to); } // 웜홀 (단방향 음수간선) for (int i = 0; i < W; i++) { st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int val = Integer.parseInt(st.nextToken()); connInfo.add(new int[]{from, to, -val}); //union(from, to); // 웜홀도 연결 정보로 간주(연결 요소 분리 목적) } } }

제출 #100949

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: