BaekJoon 14938번: 서강그라운드(C++)

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

14938번: 서강그라운드

풀이법

1) 다익스트라를 반복하여 문제를 해결하면 쉽게 풀 수 있는 문제이다.

2) ans라는 배열에 각 start Node로 부터의 거리를 담아 최대 값을 찾으면 해결이 가능하다.

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

int n, m, r;
int arr[101][101];
int item[101];
int ans[101];
int answer = 0;
void dijk(int start)
{
	for (int i = 1; i <= n; i++)
		ans[i] = INF;
	ans[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
	pq.push({ 0,start });
	while (!pq.empty())
	{
		int cost = pq.top().first;
		int curIndex = pq.top().second;
		pq.pop();

		if (cost > ans[curIndex])
			continue;
		for (int i = 1; i <= n; i++)
		{
			if (arr[curIndex][i] != INF)
			{
				int nextCost = cost + arr[curIndex][i];
				if (nextCost < ans[i])
				{
					ans[i] = nextCost;
					pq.push({ nextCost,i });
				}
			}
		}
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		item[i] = a;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			arr[i][j] = INF;
	}
	for (int i = 0; i < r; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (arr[a][b] != INF)
		{
			arr[a][b] = min(arr[a][b],c);
			arr[b][a] = min(arr[b][a],c);
		}
		else
		{
			arr[a][b] = c;
			arr[b][a] = c;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		dijk(i);//i에서 출발하는 다익스트라
		int tempMax = 0;
		for (int j = 1; j <= n; j++)
		{
			if (ans[j] <= m)
				tempMax += item[j];
		}
		answer = max(answer, tempMax);
	}
	cout << answer;
}