[백준 14938] 서강그라운드 (C++)

문제 링크: www.acmicpc.net/problem/14938

14938번: 서강그라운드

1. 주의할 점

- 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 각 Node마다 보유한 아이템의 수를 Item[] 배열에 담는다

- 플로이드 와샬 알고리즘을 사용하기 위해 Arr[][] 배열을 미리 초기화한다

- 간선이 주어진 경우, Arr[][]에 대입한다

- 플로이드 와샬 알고리즘을 수행한 후, 각 지점마다 수색범위 D를 넘지 않을 경우, Temp에 해당 지역이 보유한 아이템의 수를 모두 더한다.

- Temp와 Result를 비교하며 최대값을 Result에 저장한다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
using namespace std;
int node, d, road, a, b, val, result = 0;
int item[101];
int arr[101][101];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> d >> road;
	for (int i = 1; i <= node; i++)
		cin >> item[i];
	for (int i = 1; i <= node; i++) 
		for (int j = 1; j <= node; j++) 
			if(i!=j)	arr[i][j] = MAX;
	for (int i = 0; i < road; i++) {
		cin >> a >> b >> val;
		arr[a][b] = val;
		arr[b][a] = val;
	}	
	for (int k = 1; k <= node; k++) 
		for (int i = 1; i <= node; i++) 
			for (int j = 1; j <= node; j++)
				if (arr[i][j] > arr[i][k] + arr[k][j])
					arr[i][j] = arr[i][k] + arr[k][j];

	for (int i = 1; i <= node; i++) {
		int temp = 0;
		for (int j = 1; j <= node; j++)
			if (arr[i][j] <= d)
				temp += item[j];
		result = max(result, temp);
	}
	cout << result;
	return 0;
}