import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); final int TEST_CASE = Integer.parseInt(br.readLine()); for (int i = 0; i < TEST_CASE; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); // 건물의 개수 int numBuildings = Integer.parseInt(st.nextToken()); // 건물 순서 개수 int numSteps = Integer.parseInt(st.nextToken()); // 각 건물의 비용 int[] buildingCost = new int[numBuildings + 1]; // 차수별 최대값 int[] answerCost = new int[numBuildings]; // 각 건물의 비용에 대한 값 추가 st = new StringTokenizer(br.readLine()); for (int j = 1; j <= numBuildings; j++) { buildingCost[j] = Integer.parseInt(st.nextToken()); } // 순서에 따른 그래프 초기화 List> graph = new ArrayList<>(); for (int j = 0; j <= numBuildings; j++) { graph.add(new ArrayList<>()); } HashSet findRoot = new HashSet<>(); HashSet notUsed = new HashSet<>(); for (int j = 1; j <= numBuildings; j++) { findRoot.add(j); notUsed.add(j); } // 그래프에 값 추가 for (int j = 0; j < numSteps; j++) { st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); notUsed.remove(from); notUsed.remove(to); findRoot.remove(to); graph.get(from).add(to); } // 목표 건물 번호 int finalTarget = Integer.parseInt(br.readLine()); PriorityQueue queue = new PriorityQueue<>(); boolean flag = false; for (int key : findRoot) { if (key == finalTarget) { sb.append(buildingCost[key]).append("\n"); flag = true; break; } } if (flag) { continue; } for (int key : notUsed) { findRoot.remove(key); } for (int key : findRoot) { queue.add(new NodeJS(0, 0, key)); } int answer = 0; while (!queue.isEmpty()) { NodeJS polled = queue.poll(); int curDegree = polled.degree; int curFrom = polled.from; int curTo = polled.to; if (curTo == finalTarget) { for (int cost : answerCost) { answer += cost; } answer += buildingCost[finalTarget]; sb.append(answer).append("\n"); break; } answerCost[curDegree] = Math.max(answerCost[curDegree], buildingCost[curTo]); for (int next : graph.get(curTo)) { queue.add(new NodeJS(curDegree + 1, curTo, next)); } } } br.close(); System.out.print(sb); } static class NodeJS implements Comparable { int degree; int from; int to; public NodeJS(int degree, int from, int to) { this.degree = degree; this.from = from; this.to = to; } @Override public int compareTo(NodeJS other) { return this.degree - other.degree; } } }

제출 #98010

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: