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

[문제링크]

14938번: 서강그라운드

 

0. m 이하의 cost로 방문 가능한 노드가 가장 많은 노드 찾기

• 다익스트라를 n번 돌리거나, 플로이드-와샬 진행

 

1. 편의를 위해, 갈 수 없는 노드는 큰 값(2000)으로 초기화한다

• 최대 거리가 15, 노드가 100개이므로 두 노드의 거리는 15*99=1485가 최대값이다

 

2. 노드 간 거리 정보를 저장하고, 플로이드-와샬을 진행해 각 노드간 거리를 구한다

 

3. 각 노드 별 방문 가능한 노드들로부터 획득 아이템 갯수를 종합, 최댓값을 출력한다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int r = pint(st.nextToken());
		
		int[][]map=new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(map[i], 2000);
		}
		int[] item=new int[n];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			item[i]=pint(st.nextToken());
		}
		
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = pint(st.nextToken())-1;
			int n2 = pint(st.nextToken())-1;
			int c = pint(st.nextToken());
			
			map[n1][n2]=c;
			map[n2][n1]=c;
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				if(i==k)continue;
				for (int j = 0; j < n; j++) {
					if(i==j)continue;
					map[i][j]=Math.min(map[i][j],map[i][k]+map[k][j]);
				}
			}
		}
		
		int max_item=0;
		for (int i = 0; i < n; i++) {
			map[i][i]=0;
			int temp=0;
			for (int j = 0; j < n; j++) {
				if(map[i][j]<=m) {
					temp+=item[j];
				}
			}
			max_item=Math.max(temp, max_item);
		}
		System.out.println(max_item);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면