import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main { static Map> nodes = new HashMap<>(); static int[][] times; static class Node { private int pos; private int time; public Node(final int pos, final int time) { this.pos = pos; this.time = time; } @Override public boolean equals(final Object o) { if (o == null || getClass() != o.getClass()) { return false; } final Node node = (Node) o; return pos == node.pos; } @Override public int hashCode() { return Objects.hashCode(pos); } } 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 T = Integer.parseInt(br.readLine()); StringTokenizer st; for (int i = 0; i < T; i++) { st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int W = Integer.parseInt(st.nextToken()); for (int j = 0; j < M; j++) { // 일반 도로 st = new StringTokenizer(br.readLine()); int S = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(st.nextToken()); int time = Integer.parseInt(st.nextToken()); List value = nodes.getOrDefault(S, new ArrayList<>()); if (value.contains(new Node(E, time))) { int nodePos = value.indexOf(new Node(E, time)); Node node = value.get(nodePos); node.time = Integer.min(node.time, time); } else { value.add(new Node(E, time)); nodes.put(S, value); } } for (int j = 0; j < W; j++) { // 웜홀 st = new StringTokenizer(br.readLine()); int S = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(st.nextToken()); int time = Integer.parseInt(st.nextToken()); List value = nodes.getOrDefault(S, new ArrayList<>()); if (value.contains(new Node(E, time))) { int nodePos = value.indexOf(new Node(E, time)); Node node = value.get(nodePos); node.time = Integer.min(node.time, -time); } else { value.add(new Node(E, -time)); nodes.put(S, value); } } times = new int[N + 1][N + 1]; for (int j = 0; j < times.length; j++) { for (int k = 0; k < times[0].length; k++) { times[j][k] = Integer.MAX_VALUE / 2; } } for (Integer integer : nodes.keySet()) { bfs(integer, new boolean[N + 1]); } validete(bw); } bw.flush(); } private static void validete(final BufferedWriter bw) throws IOException { for (int j = 1; j < times.length; j++) { for (int k = 1; k < times[0].length; k++) { if (times[j][k] + times[k][j] < 0) { bw.append("YES").append("\n"); return; } } } bw.append("NO").append("\n"); } private static void bfs(int startPos, boolean[] visit) { PriorityQueue deque = new PriorityQueue<>(Comparator.comparingInt(o -> o.time)); deque.add(new Node(startPos, 0)); while (!deque.isEmpty()) { Node node = deque.poll(); visit[node.pos] = true; times[startPos][node.pos] = Integer.min(times[startPos][node.pos], node.time); List loads = nodes.getOrDefault(node.pos, new ArrayList<>()); for (Node load : loads) { int nextPos = load.pos; int nextTime = node.time + load.time; if (!visit[nextPos]) { deque.add(new Node(nextPos, nextTime)); } } } } }

제출 #131190

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: