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

이 문제는 다익스트라 알고리즘을 사용해서 풀었다.

 

이 문제는 얼핏 보면 그냥 dfs와 같은 방식으로 풀릴 것 같지만, 그렇지 않다.

어떤 점에서 다른 점으로 가는 방식이 여러가지라면, 그 중에 가장 cost가 적게 드는 방법으로 가야 한다.

 

이를 위해 다익스트라 알고리즘을 사용해서 nextCost가 m보다 작거나 같을 때까지 실행한다.

이 때 주의할 점은 다익스트라 알고리즘을 돌리는 와중에 아이템 개수를 추가하면 오답이 나온다. 이는 다익스트라 알고리즘 특성상 이미 방문했더라도 더 짧으면 다시 방문할 수도 있기 때문이다.

따라서 다익스트라 알고리즘을 다 돌린 뒤에 INF가 아닌 점들의 개수를 더해주면 정답이 나온다.

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX 100
#define INF 1000000000

struct Edge {
	int num;
	int weight;
};
struct Compare {
	bool operator() (Edge &a, Edge &b) {
		return a.weight > b.weight;
	}
};

int section[MAX + 1];
int n, m, r;
vector<Edge> edges[MAX + 1];

void input() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> section[i];
	}
	for (int i = 0; i < r; i++) {
		int a, b, l;
		cin >> a >> b >> l;
		edges[a].push_back({ b, l });
		edges[b].push_back({ a, l });
	}
}

int dijkstra(int start) {
	priority_queue<Edge, vector<Edge>, Compare> pq;
	vector<int> dist(n + 1, INF);
	dist[start] = 0;
	pq.push({ start, 0 });

	while (!pq.empty()) {
		int present = pq.top().num;
		int cost = pq.top().weight;
		pq.pop();

		for (Edge &edge : edges[present]) {
			int next = edge.num;
			int nextCost = cost + edge.weight;

			if (dist[next] > nextCost && nextCost <= m) {
				dist[next] = nextCost;
				pq.push({ next, nextCost });
			}
		}
	}

	int result = 0;
	for (int i = 1; i <= n; i++) {
		if (dist[i] != INF) {
			result += section[i];
		}
	}

	return result;
}

int solve() {
	int result = -1;
	for (int i = 1; i <= n; i++) {
		result = max(result, dijkstra(i));
	}
	return result;
}

int main() {
	input();
	cout << solve() << '\n';
	return 0;
}