문제

출발점이 주어지지 않았으므로, 모든 노드를 출발점으로 하여 다익스트라를 n번 돌린다. 그리고 dist를 다 계산한 후에 출발점에 대해 거리가 m 이하인 노드들의 아이템 수만 더해주면 된다.

다익스트라 읽어보기

구현

#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#include <algorithm> // max
#define MAX 101
#define INF 0x7FFFFFFF
using namespace std;

vector<int> item(MAX);
vector< pair<int, int> > graph[MAX]; // graph[from] = ((to, weight), (to, weight), ...)
vector<int> dist(MAX, INF);
int n, m, answer;

int dijkstra(int start) {
	int i;
	priority_queue < pair<int, int>, vector< pair <int, int> >, greater< pair<int, int> > > pq; // (weight, from)

	for (i = 0; i < MAX; i++) dist[i] = INF;

	dist[start] = 0;
	pq.push(make_pair(0, start));

	while (!pq.empty()) {
		int weight = pq.top().first;
		int from = pq.top().second;
		pq.pop();

		if (dist[from] < weight) continue;

		int edges = graph[from].size();
		for (i = 0; i < edges; i++) {
			int to = graph[from][i].first;
			int newDist = weight + graph[from][i].second;

			if (newDist < dist[to]) {
				dist[to] = newDist;
				pq.push(make_pair(newDist, to));
			}
		}
	}

	int ans = 0;
	for (i = 1; i <= n; i++) {
		if (dist[i] <= m) ans += item[i];
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int r, a, b, I, i;
	cin >> n >> m >> r;

	for (i = 1; i <= n; i++) cin >> item[i];
	for (i = 1; i <= r; i++) {
		cin >> a >> b >> I;
		graph[a].push_back(make_pair(b, I));
		graph[b].push_back(make_pair(a, I));
	}

	for (i = 1; i <= n; i++) answer = max(answer, dijkstra(i));
	cout << answer << endl;
	return 0;
}