[BOJ] 백준 14938번: 서강그라운드

모든 지점에서 다익스트라를 반복하여 최대값을 찾는 문제

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
vector<pii> v[101];
int dist[101];
int item[101];
int n, m, r;
bool visit[101] = { 0, };
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 >> item[i];
	}
	for (int i = 0; i < r; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		priority_queue<pii, vector<pii> > pq;
		fill(dist, dist + n + 1, 2e9);
		fill(visit, visit + n + 1, 0);
		pq.push({ 0,i });
		dist[i] = 0;
		while (!pq.empty()) {
			int node = pq.top().second;
			visit[node] = 1;
			pq.pop();
			for (auto nxt : v[node]) {
				int next = nxt.first;
				int cost = nxt.second;
				if (dist[next] > dist[node] + cost) {
					dist[next] = dist[node] + cost;
					if (dist[next] <= m) {
						pq.push({ -dist[next] , next });
					}
				}
			}
		}
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (visit[j]) {
				cnt += item[j];
			}
		}
		ans = max(cnt, ans);
	}
	cout << ans;
}