import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ private static int n, m, r; private static int[] items; private static List> roadmap = new ArrayList<>(); private static boolean[] visited; private static int result; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); r = Integer.parseInt(st.nextToken()); visited = new boolean[n]; items = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { items[i] = Integer.parseInt(st.nextToken()); } for (int i = 0; i < n; i++) { roadmap.add(new ArrayList<>()); } for (int i = 0; i < r; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int l = Integer.parseInt(st.nextToken()); roadmap.get(a - 1).add(new int[]{b - 1, l}); roadmap.get(b - 1).add(new int[]{a - 1, l}); } for (int i = 0; i < n; i++) { getItems(i); } System.out.println(result); } private static void getItems(int region) { Arrays.fill(visited, false); Queue queue = new LinkedList<>(); queue.offer(new int[]{region, 0}); visited[region] = true; int totalItems = 0; while (!queue.isEmpty()) { int[] curNode = queue.poll(); int curRegion = curNode[0]; int curWeight = curNode[1]; totalItems += items[curRegion]; for (int[] nxtNode : roadmap.get(curRegion)) { int nxtRegion = nxtNode[0]; int nxtWeight = nxtNode[1]; if (visited[nxtRegion]) { continue; } if (curWeight + nxtWeight > m) { continue; } queue.offer(new int[]{nxtRegion, curWeight + nxtWeight}); visited[nxtRegion] = true; } } result = Math.max(result, totalItems); } }

제출 #172429

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: