백준[14938] 서강그라운드

아이디어

• 다익스트라 알고리즘을 사용할 수 있다.

풀이

1. 각 노드별로 거리와 다음 노드를 저장한다.
2. 다익스트라 알고리즘을 사용해서 각 노드에서 다른노드까지의 최단거리를 구한다.
3. 반복문을 통해 각 노드에서 내렸을 때 다른노드까지의 최단거리가 m보다 작거나 같다면 획득 가능 아이템으로 추가하고, max()를 이용하여 가장 큰 값을 찾는다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <math.h>
#define MAX_VALUE 987654321

using namespace std;

int n, m, r;

int supply[101];

vector<pair<int,int>> node[101];
int dp[101][101];

void dijkstra(int first) {
	dp[first][first] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,first });

	while(!pq.empty()) {
		int now_node = pq.top().second;
		int now_len = -pq.top().first;
		pq.pop();

		if (dp[first][now_node] < now_len) continue;

		for (pair<int, int> next : node[now_node]) {
			int next_node = next.second;
			int next_len = next.first + now_len;

			if (next_len < dp[first][next_node]) {
				dp[first][next_node] = next_len;
				pq.push({ -next_len,next_node });
			}
		}
	}
}


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++) {
		int num; cin >> num;
		supply[i] = num;
		for (int j = 1; j <= n; j++) {
			dp[i][j] = MAX_VALUE;
		}
	}

	for (int i = 1; i <= r; i++) {
		int a, b, l; cin >> a >> b >> l;
		node[a].push_back({ l,b });
		node[b].push_back({ l,a });
	}

	for (int i = 1; i <= n; i++) {
		dijkstra(i);
	}

	int ans = 0;

	for (int i = 1; i <= n; i++) {
		int temp = 0;
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] <= m) temp += supply[j];
		}
		ans = max(temp, ans);
	}

	cout << ans;

	return 0;
}

평가

다익스트라 알고리즘만 잘 알고 있다면 충분히 풀 수 있는 문제.
n이 100이기에 플로이드-워셜 알고리즘을 사용해도
O(n^3)의 시간복잡도로도 충분할 것이기에, 플로이드 워셜알고리즘을 사용한다면
더욱 쉽게 풀이할 수 있습니다.