데이크스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구하는 알고리즘이다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;


priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
int n, m, r;
//위치 아이템
int goods[101];
//거리 저장
int li[101];
vector<pair<int,int>> v[101];
int result = 0;

void dij(int x) {

	for (int i = 1; i <= n; i++)
		li[i] = INF;

	li[x] = 0;

	pq.push({ 0,x });
	//거리 ,위치 
	//거리가 작은 순서대로 방문하고 만약 그곳 방문했으면 다시방문 안해도됨
	while (!pq.empty()) {
		int distance = pq.top().first;
		int point = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[point].size(); i++) {
			int next_point = v[point][i].first;
			int next_distance = v[point][i].second;
			int sum_distance = distance + next_distance;
			//탐색 가능한 범위내에 있을때
			if (sum_distance < li[next_point]) {
				li[next_point] = sum_distance;
				pq.push({ sum_distance, next_point });
			}
		}
	}
	int cur_result = 0;
	
	for (int i = 1; i <= n; i++) {
		if (li[i] <= m) {
			cur_result += goods[i];
		}
	}

	result = max(cur_result, result);
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> r;

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

	for (int i = 0; i < r; i++) {
		//c는 탐색범위임
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}

	for (int i = 1; i <= n; i++) {
		//예은이가 1번 지역부터 n번 지역까지 가는 경우의 수에서 검사
		dij(i);
	}

	cout << result;

	return 0;
}