14938 서강그라운드

알고리즘(플로이드워셜)

1. 접근 방법
	- 처음엔 DFS 또는 BFS로 접근
	- 근데 해보니 이전에 왔던 것보다 적은 거리를 써서온건 보내고, 보낸 다음부터 이어지는 건 겹치면 빼야함.
	- 결국 플로이드워셜로 최소거리를 모두 구한 후, 탐색범위 안에 들어오는 지역의 아이템을 모두 더하는 방식과 동일함.

코드

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
 
int n, m, r, t, item[31], area[31][31];
int check[31];
list<pair<int, pair<int, int>>> q;
 
int floyd();
int max(int a, int b) {
	return a > b ? a : b;
}
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++)
		cin >> item[i];
 
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			if (i != j)
				area[i][j] = 200000000;
 
	for (int i = 0; i < r; i++) {
		int a, b, c;
		cin >> a >> b >> c;
 
		if (c < area[a][b]) {
			area[a][b] = c;
			area[b][a] = c;
		}
	}
	cout << floyd() << endl;
}
 
int floyd() {
	int result = 0;
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (area[j][k] > area[j][i] + area[i][k])
					area[j][k] = area[j][i] + area[i][k];
			}
		}
	}
 
	for (int i = 1; i <= n; i++) {
		int temp = 0;
		for (int j = 1; j <= n; j++) {
			if (area[i][j] <= m)
				temp += item[j];
		}
		result = max(result, temp);
	}
	return result;
}