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

이 문제는 낙하한 지역을 중심으로 수색 범위 m이내의 모든 지역의 아이템을 습득 가능할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 구해야 한다.

먼저, 낙하 지점을 선택해야하며, 낙하 지점에서 다른 지역으로의 최단 경로가 수색 범위 이내인지 확인한 뒤, 얻을 수 있는 아이템의 개수를 구할 수 있다.

따라서, 먼저 모든 정점에 대한 다른 정점으로의 최단 경로를 구하는 과정이 필요한데, 이를 플로이드 워셜 알고리즘으로 해결할 수 있다.

이후, 낙하 지점 i에서 다른 정점 j로의 최단 경로는 w[i][j]가 될 것이다. 이 때, w[i][j] <= m인 경우만 아이템을 획득 가능하므로 이 경우만 누적합하여 낙하 지점 i에서의 획득 가능한 아이템의 갯수를 구할 수 있다. 이것의 최댓값을 ans에 저장해주면 끝인 문제이다.

따라서, 플로이드 워셜 알고리즘의 시간 복잡도 $O(V^3)$과 최댓값을 구할 때의 시간 복잡도 $O(V^2)$으로 전체 시간 복잡도는 $O(V^3)$으로 1초 이내에 정답을 구할 수 있다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 100;
int n, m, r;
int w[101][101], item[101], ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		fill(w[i], w[i] + n + 1, INF);
		w[i][i] = 0;
	}
	for (int i = 1; i <= n; i++) cin >> item[i];
	for (int i = 0, a, b, l; i < r; i++) {
		cin >> a >> b >> l;
		w[a][b] = min(w[a][b], l);
		w[b][a] = min(w[b][a], l);
	}

	// 플로이드로 최단 경로 구하기
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
			}
		}
	}

	// 각 지점에서 최단 경로가 m이하인 지점의 아이템 합 구하기
	for (int i = 1; i <= n; i++) {
		int tot = 0;
		for (int j = 1; j <= n; j++) {
			if (w[i][j] <= m) tot += item[j];
		}
		ans = max(ans, tot);
	}
	cout << ans;
}