[알고리즘] 백준 14938번: 서강그라운드 (C++)

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

14938번: 서강그라운드

판단 실수로 플로이드 와샬 안에서도 최단 경로를 갱신할 때 m(수색 범위) 이내에 있는 것만 갱신해줬었다.

어쨌거나 최단 경로들은 모두 갱신한 후에 m(수색 범위) 안에서 갈 수 있는 길을 찾아야 하는 것이 포인트다.

#include <iostream>
#include <cmath>
#define MAX 100 + 1
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int item[MAX];
int n, m, r;

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		graph[i][i] = 0;
	}
}

int main() {
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> item[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < r; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
		graph[b][a] = c;
	}

	floydWarshall();

	int maxValue = 0;
	for (int i = 1; i <= n; i++) {
		int sum = 0;
		for (int j = 1; j <= n; j++) {
			if (graph[i][j] <= m) {
				sum += item[j];
			}
		}
		maxValue = max(maxValue, sum);
	}

	cout << maxValue;
	return 0;
}