[백준] 14938_서강그라운드_플로이드 워셜

[문제 링크] boj 14983 서강 그라운드 플로이드워셜 

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

14938번: 서강그라운드

[생각 흐름]

처음에는 예시에서 한 지점을 두고 설명하길래 다익스트라로 해결하는 문제인 줄 알았는데 input값을 보고 플로이드 워셜로 해결해야겠다고 생각했다.

플로이드 워셜로 위치에서의 가장 짧은 distance를 구한후에, 각 지점에서 탐색 가능한 범위인 경우 stock[city]를 더하여 저장하고 

값들 중 최대값을 계산하여 출력하였다.

 

[코드]

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

public class Main {
    private static final int INF = (int) 1e9;
    public static void main (String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int city = Integer.parseInt(st.nextToken());
        int available=Integer.parseInt(st.nextToken());
        int line = Integer.parseInt(st.nextToken());

        int stock[] = new int[city];
        st= new StringTokenizer(br.readLine());
        for(int i=0;i<city;i++) stock[i] = Integer.parseInt(st.nextToken());

        //배열 초기화ㅡ자기자신은 0 
        int arr[][] = new int [city][city];
        for(int i=0;i<city;i++){
            Arrays.fill(arr[i],INF);
            arr[i][i]=0;
        }

        for(int i=0;i<line;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int d = Integer.parseInt(st.nextToken());
            arr[a][b]=arr[b][a]=d;
        }


        //플로이드 워셜
        for(int i=0;i<city;i++){
            for(int p=0;p<city;p++){
                for(int q=0;q<city;q++){
                    arr[p][q]= Math.min(arr[p][q],arr[p][i]+arr[i][q]);
                }
            }
        }

        int max =0;
        for(int i=0;i<city;i++){
            int temp=0;
            for(int j=0;j<city;j++){
                if(arr[i][j]<=available)temp+= stock[j];
            }
            max= Math.max(temp,max);
        }

        System.out.println(max);

    }
}