import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; 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[] visited; 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() { visited[connInfo.get(0)[0]] = 0; for (int i = 0; i < N - 1; i++) { for (int j = 0; j < connInfo.size(); j++) { int from = connInfo.get(j)[0]; int to = connInfo.get(j)[1]; int val = connInfo.get(j)[2]; if (visited[from] != Integer.MAX_VALUE) { if (visited[to] > visited[from] + val) { visited[to] = visited[from] + val; } } } } //음수 사이클을 찾기위해 다시 반복 for (int i = 0; i < N - 1; i++) { for (int j = 0; j < connInfo.size(); j++) { int from = connInfo.get(j)[0]; int to = connInfo.get(j)[1]; int val = connInfo.get(j)[2]; if (visited[to] > visited[from] + val) { //음수 사이클 존재! answerString.append("YES").append("\n"); return; } } } answerString.append("NO").append("\n"); } 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()); visited = new int[N + 1]; for (int i = 0; i < N + 1; i++) { visited[i] = Integer.MAX_VALUE; } connInfo = new ArrayList<>(); 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}); } 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}); } } }

제출 #100882

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: