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

문제 링크입니다. https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

다익스트라 알고리즘을 사용하는 문제입니다.

X번 지점에서 시작했을 때, 수색 범위 내에 얻을 수 있는 아이템의 최댓값을 구하는 문제입니다.

 

저는 1 ~ N번까지 각각의 그래프를 확인한 뒤, 해당 그래프에서 얻을 수 있는 아이템의 값을 구하고 값들을 전부 확인하게습니다.

 

다음 그림을 통해 확인해보겠습니다.

위 그림과 같은 방식으로 아이템의 최댓값을 구하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 비용, 위치
int N, M, R;
int item[101];
int Distance[101];
vector<pair<int, int>> line[101];

void Dijstra(int x) {
	for (int i = 1; i <= N; i++) Distance[i] = INF;
	Distance[x] = 0;
	q.push({ 0,x });
	while (!q.empty()) {
		int X = q.top().second;
		int cost = q.top().first;
		q.pop();
		for (int i = 0; i < line[X].size(); i++) {
			int xx = line[X][i].first;
			int Cost = line[X][i].second;
			if (Distance[xx] > Distance[X] + Cost) {
				Distance[xx] = Distance[X] + Cost;
				q.push({ Distance[xx] , xx });
			}
		}
	}
}

int find_cost(int x) {
	int cost = 0;
	for (int i = 1; i <= N; i++) {
		if (Distance[i] <= M) {
			cost += item[i];
		}
	}
	return cost;
}

void solve() {
	int maxi = 0;
	for (int i = 1; i <= N; i++) {
		Dijstra(i);
		maxi = max(maxi, find_cost(i));
	}
	cout << maxi;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> R;
	for (int i = 1; i <= N; i++) {
		cin >> item[i];
	}
	for (int i = 1; i <= R; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		line[x].push_back({ y,cost });
		line[y].push_back({ x,cost });
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요