[BOJ] 14938. 서강그라운드 (C++)

문제

각 지역이 일정한 길이의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수

생각할 것

• 예은이의 출발 위치가 정해져 있지 않으므로 플로이드 워셜을 사용해보자!
• 각 지역에서의 거리를 모두 구한 뒤, 각 지역에서 탐색할 수 있는 지역만큼 아이템을 더해준다

코드

#include <iostream>
#include <vector>

#define INF 1e9

using namespace std;

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

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

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

    vector<vector<int>> adj(n + 1, vector<int>(n + 1, INF));
    int a, b, l;
    for (int i = 0; i < r; i++) {
        cin >> a >> b >> l;
        adj[a][b] = l; // 양방향 입력
        adj[b][a] = l;
    }

    for (int i = 1; i <= n; i++) adj[i][i] = 0;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    int res = 0, tmp = 0;
    for (int i = 1; i <= n; i++) { // 예은이가 내리는 지역
        tmp = 0;
        for (int j = 1; j <= n; j++) { // 탐색 할 지역
            if (adj[i][j] <= m) {
                tmp += item[j];
            }
        }
        res = max(res, tmp);
    }

    cout << res;

    return 0;
}