BOJ 14938 : 서강그라운드

• 문제 링크 : boj.kr/14938
• 난이도 : G4
• 태그 : 플로이드 워셜

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, m, r;
    cin >> n >> m >> r;

    vector<int> items(n);
    for(auto &u : items) cin >> u;

    vector<vector<int>> arr(n, vector<int>(n, INF));
    for(int i = 0; i < r; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        arr[a-1][b-1] = c;
        arr[b-1][a-1] = c;
    }
    for(int i = 0; i < n; i++) {
        arr[i][i] = 0;
    }

    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            if(arr[i][j] <= m) sum += items[j];
        }
        ans = max(ans, sum);
    }
    cout << ans;

    return 0;
}

---

풀이

각 노드 사이의 모든 거리를 플로이드 워셜로 구한다.

이후 어떤 한 노드에서 다른 노드들까지의 거리가 조건 m을 만족하는 노드들의 아이템의 수의 합을 구하고, 최댓값을 구해주면 된다.