[BOJ / C++] 서강그라운드 (골드4 - 플로이드)

문제링크: https://www.acmicpc.net/problem/14938

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = (INT_MAX / 2) - 1;

int main() {
    ios::sync_with_stdio(0);
    cin.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>> d(n+1, vector<int>(n+1, INF));
    
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

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

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

    int mx = 0;
    for (int i = 1; i <= n; i++) {
        int gettable = 0;
        for (int j = 1; j <= n; j++) {
            if (d[i][j] <= m) gettable += item[j];
        }

        if (gettable > mx) mx = gettable;
    }
    cout << mx;
}

 

 

2. 시간복잡도

• 플로이드 워셜 알고리즘으로 3중 for문을 돌며 d 테이블을 채우는데 가장 많은 시간이 걸린다.
• n=100으로 (10^2)^3 = 10^6 < 10^8 이므로 시간제한 1초 내에 통과 가능하다. 
• 플로이드 워셜 알고리즘은 주로 단순 계산 대입이 많으므로 n=1000 (10^3)까지 시간내 통과 가능하다.

 

3. 분석

 

플로이드 알고리즘의 d 테이블을 채우고 d 테이블의 i → j의 길이는 전부 최단 경로가 된다. i에서 j로 가는 최단경로가 수색범위 m보다 작을 때만 아이템을 얻을 수 있는 것이다. 따라서 최단경로가 수색범위 이내이면 해당 지점의 아이템을 gettable에 추가하는 방식으로 i지점에서 수색범위 내의 아이템을 모두 더한다.

 

이후 i를 증가시키면서 mx를 갱신하여 전체 최댓값을 구해주면 된다.