골드4 - 백준 14938 서강그라운드

백준 14938 서강그라운드

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

접근방법

모든 노드에 대해서 해당 노드에서 갈 수 있는 범위 내의 모든 노드의 아이템 개수를 더해서 최대값을 구해주어야 한다. 따라서 플로이드 와샬 알고리즘을 이용해서 각 노드에서 다른 노드까지의 최단거리를 전부 구해주었고 범위 안에 있는 아이템 개수들을 구해주었다.

풀이

중복된 입력을 고려하여 route배열에 최소 입력값만 저장되게끔 처리해주었고, 플로이드 와샬 알고리즘을 써서 route배열에 최소 거리들을 구해 저장해주었다. 그리고 모든 노드들을 순회하면서 범위 내의 아이템들을 sum에 더해주었고, result와 비교해서 가장 큰 값으로 갱신되게끔 처리해주었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int items[101];
int route[101][101];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, R;
	cin >> N >> M >> R;

	for (int i = 1; i <= N; i++)
	{
		cin >> items[i];
		for (int j = 1; j <= N; j++)
		{
			if (i == j)
				route[i][j] = 0;
			else
				route[i][j] = 100000;
		}
	}

	for (int i = 0; i < R; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (route[a][b] > c)
		{
			route[a][b] = c;
			route[b][a] = c;
		}
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
				route[i][j] = min(route[i][j], route[i][k] + route[k][j]);
		}
	}

	int result = -1;
	for (int i = 1; i <= N; i++)
	{
		int sum = 0;
		for (int j = 1; j <= N; j++)
		{
			if (route[i][j] <= M)
				sum += items[j];
		}
		result = max(sum, result);
	}

	cout << result << endl;
	return 0;
}