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

출처 : https://www.acmicpc.net/problem/14938

 

모든 정점을 돌면서 다익스트라를 이용해서 정점까지의 거리가 m 이하면 아이템의 개수를 더해서 아이템이 가장 많은 정점을 찾았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m, r;
vector<int> Item;
vector<vector<pair<int, int>>> graph;

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

int Dijkstra(int start) {

	vector<int> best(n + 1, INT_MAX);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;

	pq.push({ start,0 });
	best[start] = 0;

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

		int vertex = curr.vertex;
		int cost = curr.cost;
		if (cost > best[vertex])
			continue;

		for (auto next : graph[vertex]) {
			int nextCost = cost + next.second;
			if (nextCost >= best[next.first])
				continue;

			best[next.first] = nextCost;
			pq.push({ next.first,nextCost });
		}
	}
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		if (best[i] <= m) ret += Item[i];
	}
	return ret;
}

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

	cin >> n >> m >> r;
	Item = vector<int>(n + 1);
	graph = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>());
	for (int i = 1; i <= n; i++) {
		cin >> Item[i];
	}
	for (int i = 0; i < r; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		graph[a].push_back({ b,d });
		graph[b].push_back({ a,d });
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, Dijkstra(i));
	}
	cout << ans;
};