BOJ_14938_서강그라운드_java

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

14938번: 서강그라운드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 백준 14938 서강그라운드
 골드 4
 */
public class BOJ_14938_서강그라운드 {
    final static int max = 123456789;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 지역의 개수
        int m = Integer.parseInt(st.nextToken()); // 수색범위
        int r = Integer.parseInt(st.nextToken()); // 길의 개수

        int item[] = new int[n+1]; // 각 지역의 아이템 수

        int[][] roads = new int[n+1][n+1];
        for (int i = 1; i<n+1; i++){
            for (int j = 1; j<n+1; j++){
                roads[i][j] = max;
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i<=n; i++){
            item[i] = Integer.parseInt(st.nextToken());
        }
        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());
            roads[a][b] = l;
            roads[b][a] = l;
        }
        //플로이드 와샬
        for (int i = 1; i<n+1; i++){ // 경유지
            for (int j = 1; j<n+1; j++){ //출발지
                for (int k = 1; k<n+1; k++){ // 도착지
                    if(i == j || j ==k || i == k) continue;
                    roads[j][k] = Math.min(roads[j][k], roads[j][i] + roads[i][k]);
                }
            }
        }

        int ans = 0;
        for (int i = 1; i<n+1; i++){ // 출발지 i일때 최대 값 구하기
            int tmp = item[i];
            for (int j = 1; j<n+1; j++){
                if (roads[i][j] <= m){
                    tmp += item[j];
                }
                ans = Math.max(ans, tmp);
            }
        }
        System.out.println(ans);
    }
}