c++ 백준_14938_"서강그라운드"

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

14938번: 서강그라운드

 

​

floyd 알고리즘을 사용해

각 지점에서 각 지점까지의 최단거리를 다 구해서

갈 수 있는 방향에 item 개수를 더하였다.

​

#include <iostream>
#include <vector>
using namespace std;

#define INF 1000000000

int path[101][101];
int item[101];
int n, m, r;

void floyd() {

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


int main(void) {

	
	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 <= i; j++) {
			path[i][j] = INF;
			path[j][i] = INF;
		}
		path[i][i] = 0;
	}
	

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

	floyd();

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