[백준] 14938 서강그라운드 c++

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

14938번: 서강그라운드

 

풀이과정

자신에서 자신으로 갈 수 없으니, i == j 일 때를 제외한 나머지 부분들은 무한대로 초기 설정한다. 그리고 num 배열에 각 정점에서 얻을 수 있는 아이템이 몇 개인지 입력받는다. 플로이드 와샬을 시행했을 때, 결과는 아래 사진처럼 나오게 되는데, 여기서의 숫자들은 각 노드에서 다른 노드를 갈 때 길의 길이가 얼마인지 알려주는 숫자들이다. 수색범위가 m이니까 각 노드에서 갈 때를 비교하여 m 이상인 숫자들은 도달할 수 없는 정점이라는 뜻이니 continue로 넘어가 준다.

 

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

int n, m, r, x, y, z;
int num[101];
int arr[101][101];
const int INF = 1e9;

void floyd() {
  for (int k = 1; k <= n; k++) { // 경유지
    for (int i = 1; i <= n; i++) { // 출발지점
      for (int j = 1; j <= n; j++) { // 도착지점
        if (arr[i][j] > arr[i][k] + arr[k][j]) {
            arr[i][j] = arr[i][k] + arr[k][j];
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> r;
    // 플로이드 와샬 초기설정
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		if (i != j) arr[i][j] = INF;
    	}
    }
    for (int i = 1; i <= n; i++) cin >> num[i];
    for (int i = 0; i < r; i++) {
    	cin >> x >> y >> z;
    	arr[x][y] = z;
    	arr[y][x] = z;
    }
    floyd();

    int res = 0;
    for (int i = 1; i <= n; i++) {
    	int sum = 0;
    	for (int j = 1; j <= n; j++) {
    		if (arr[i][j] > m) continue;
    		sum += num[j];
    	}
    	res = max(res, sum);
    }
    cout << res;
}