백준 14938번 서강그라운드 문제풀이(C++)

백준 14938번 서강그라운드

아이디어

주의 깊게 봐야할 점

1. 양방향 통행 => 양방향 간선

2. 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수
   => 최단거리로 m을 체크하면서 경로마다 아이템 개수 체크 => m을 벗어나기 직전의 아이템 개수의 최대값 체크 => 다익스트라 알고리즘 사용

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 110
#define INF 2'100'000'000
int n, m, r;
int field[MAX];
int dist[MAX];
vector<pair<int, int>> v[MAX];
int getItem(int start) {
	fill(&dist[0], &dist[0] + MAX, INF);
	dist[start] = 0;
	queue<pair<int, int>> q;
	q.push({ 0,start });
	while (!q.empty()) {
		int cost = -q.front().first;
		int cur = q.front().second;
		q.pop();
		for (auto a : v[cur]) {
			int next = a.first;
			int nCost = cost + a.second;
			if (dist[next] < nCost)continue;
			q.push({ -nCost, next });
			dist[next] = nCost;
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)
		if (dist[i] <= m)sum += field[i];
	return sum;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++)
		cin >> field[i];
	while (r--) {
		int a, b, l; cin >> a >> b >> l;
		v[a].push_back({ b,l });
		v[b].push_back({ a,l });
	}
	int _max = 0;
	for (int i = 1; i <= n; i++) {
		_max = max(_max, getItem(i));
	}
	cout << _max << '\n';
	return 0;
}