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

플로이드-와샬 알고리즘으로도 풀 수 있는 문제이지만, 다익스트라가 문제를 보고 떠올랐기에 다익스트라로 풀었다

각 vertex에 대해서 다익스트라를 수행해주고, 수행 후의 distance와 m을 비교해 ans의 max값을 찾아내면 된다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
#define MAX 987654321
using namespace std;

int n, m, r;
int a, b, l;
int items[101];
vector<pii> v[101];
int dist[101];

void init() {
	for (int i = 0; i <= n; i++) {
		dist[i] = MAX;
	}
}

void dijikstra(int start) {
	init();
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty()) {
		auto cur = pq.top(); pq.pop();

		int cur_dist = cur.first;
		int cur_vertex = cur.second;

		for (int i = 0; i < v[cur_vertex].size(); i++) {
			int next_dist = v[cur_vertex][i].first;
			int next_vertex = v[cur_vertex][i].second;

			if (cur_dist + next_dist < dist[next_vertex]) {
				dist[next_vertex] = cur_dist + next_dist;
				pq.push({ dist[next_vertex], next_vertex });
			}
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> items[i];
	}

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

	int ans = -1;
	for (int i = 1; i <= n; i++) {
		dijikstra(i);
		int temp = 0;
		for (int j = 1; j <= n; j++) {
			if (dist[j] <= m)
				temp += items[j];
		}
		ans = max(temp, ans);
	}
	cout << ans << endl;

	return 0;
}