[JAVA] 백준 14938 - 서강그라운드

https://www.acmicpc.net/problem/14938

갈 수 있는 최대 경로 내에 있는 정점의 value를 모두 더하는 문제이다.

시작점도 모든 정점이 될 수 있고, 그 정점을 기준으로 구해야하는 최단경로도 모든 정점에 대해 구해야 하므로

플로이드-워셜을 써야겠다는 생각을 했고, 쉽게 풀 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] map = new int[a[0]][a[0]];
        for (int i = 0; i < map.length; i++) {
            Arrays.fill(map[i],999999);
            map[i][i] = 0;
        }
        int limit = a[1];
        int roadCount = a[2];
        int[] items = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < roadCount; i++) {
            int[] road = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map[road[0]-1][road[1]-1] = road[2];
            map[road[1]-1][road[0]-1] = road[2];
        }

        for (int k = 0; k < map.length; k++) {
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map.length; j++) {
                    if(map[i][k] + map[k][j]<map[i][j]){
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
        int[] answer = new int[map.length];
        for (int i = 0; i <map.length ; i++) {
            int count = 0;
            for (int j = 0; j < map.length; j++) {
                if(map[i][j]<=limit) count+=items[j];
            }
            answer[i] = count;
        }

        System.out.println(Arrays.stream(answer).max().getAsInt());
    }
}