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

#include <iostream>
 
int iSize[101] = {};
int graph[101][101] = {};
 
int main()
{
    int n = 0;
    int m = 0;
    int r = 0;
    std::cin >> n >> m >> r;
 
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> iSize[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            graph[i][j] = 100000000;
 
            if (i == j)
                graph[i][j] = 0;
        }
    }
 
    for (int i = 0; i < r; ++i)
    {
        int iStart = 0;
        int iEnd = 0;
        int iLong = 0;
 
        std::cin >> iStart >> iEnd >> iLong;
 
        graph[iStart][iEnd] = iLong;
        graph[iEnd][iStart] = iLong;
    }
 
    for (int k = 1; k <= n - 1; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (i == j)
                    continue;
 
                if (graph[i][k] + graph[k][j] < graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
 
    int iMax = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        int iSum = 0;
 
        for (int j = 1; j <= n; ++j)
        {
            if (graph[i][j] <= m)
            {
                iSum += iSize[j];
            }
        }
 
        iMax = std::max(iMax, iSum);
    }
 
    std::cout << iMax;
 
    return 0;
}

 

플로이드와샬 알고리즘을 이용해서 풀었습니다.

여러 개의 길을 한번에 구할 수 있기 때문에 이 알고리즘을 이용했습니다.

그 길을 다 구해서 수색범위 내에 있는 것들만 추가했습니다.