[백준] 14938번 서강그라운드 C++ 코드

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
const int INF = 987654321;
int n, m, r, visited[103], itm[103],a,b,l,res;
vector<pair<int,int>> adj[103];
// 다익스트라
// 한 점에서 이동할 수 있는 구역 거리 다 구하기
// 그 후 이동 범위 안에 있으면 개수 증가, 최대값 비교

int dijkstra(int x) {
	fill(visited, visited + 103, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
	pq.push(make_pair(0, x));
	visited[x] = 0;
	while(!pq.empty()) {
		int dist = pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if(dist > visited[here]) continue;
		for(pair<int,int> pn : adj[here]) {
			int cost = dist + pn.second;
			if(visited[pn.first] > cost) {
				visited[pn.first] = cost;
				pq.push(make_pair(cost, pn.first));
			}
		}
	}
	int cnt = 0;
	for(int i = 1; i < n + 1; i++) {
		if(visited[i] <= m) cnt += itm[i];
	}
	return cnt;
}
void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int main() {
	FASTIO();
	cin >> n >> m >> r;
	for(int i = 1; i < n + 1; i++) cin >> itm[i];
	for(int i = 0; i < r; i++) {
		cin >> a >> b >> l;
		adj[a].push_back(make_pair(b,l));
		adj[b].push_back(make_pair(a,l));
	}
	for(int i = 1; i < n + 1; i++) {
		int tmp = dijkstra(i);
		res = max(res, tmp);
	}
	cout << res << '\n';
	return 0;
}

풀이

1번부터 n번까지 다익스트라 알고리즘을 적용해서 거리를 계산하고, m 이하의 거리에 있는 아이템을 파밍해주면 된다.