[ 백준 / C++ ] 14938 : 서강그라운드

[ 문제 ]

 

14938번: 서강그라운드

 

[ 접근방법 ]

 

시작 지역을 기준으로 거리가 m 이하인 지역에 존재하는 아이템 수의 합을 구해야 한다.

 

모든 지역이 시작 지점이 될 수 있기에 플로이드-워셜 알고리즘을 활용하여 모든 최단 거리를 구하였다.

 

n ≤ 100 이므로 플로이드-워셜 알고리즘을 사용하더라도 시간은 충분하다. O(N^3)

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, r, t[105], d[105][105], INF = 10000;

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

    cin >> n >> m >> r;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        for(int j = 1; j <= n; j++){
            if(i != j){
                d[i][j] = INF;
            }
        }
    }

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

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int ans = 0;
    for(int i = 1; i <= n; i++){
        int sum = 0;
        for(int j = 1; j <= n; j++){
            if(d[i][j] <= m){
                sum += t[j];
            }
        }
        ans = max(ans, sum);
    }

    cout << ans;

    return 0;
}