[백준 14938] 서강그라운드

맨처음에는 모든 정점을 BFS로 돌렸다

 

하지만 BFS로 돌릴 시 아래와 같은 경우에

3을 먼저 방문하고 4까지 방문해서

4가 visited 처리가 되면

2번에서 4번에 방문하지 못한다

 

 

따라서 1 -> 4는 사실 2인데

1 -> 4 가 201로 되서 4까지 못간다고 판단한다

 

따라서 각 N개의 노드에서 다른 노드로 가는 최적경로를 모두 구하고

각 N개의 노드에서 타 노드로 R만큼의 거리 이내에서 갈 수 있는지 판단하는 식으로 풀어야한다

 

따라서 플로이드 워셜로 풀면 된다

 

---

#include <iostream>
#include <climits>

#define SIZE 101

using namespace std;

int dp[SIZE][SIZE];
int item[SIZE];

int N, M, R;

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

    cin >> N >> M >> R;

    // 플로이드 워셜 전 초기화
    for (int i = 1; i <= N;i++){
        for (int k = 1; k <= N;k++){
            dp[i][k] = INT_MAX;
        }
    }
    for (int i = 1; i <= N;i++) dp[i][i] = 0;

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

    int start, end, cost;
    for (int i = 0; i < R; i++)
    {
        cin >> start >> end >> cost;
        
        if(cost < dp[start][end]) {
            dp[start][end] = cost;
            dp[end][start] = cost;
        }
    }

    for (int mid = 1; mid <= N; mid++){
        for (int start = 1; start <= N; start++){
            if(dp[start][mid] == INT_MAX) continue;

            for (int end = 1; end <= N; end++)
            {
                if (dp[mid][end] == INT_MAX) continue;
                
                dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid][end]);
            }
        }
    }

    int ans = INT_MIN;

    for (int i = 1; i <= N; i++)
    {
        int sum = 0;
        for (int k = 1; k <= N; k++)
        {
            // 수색범위보다 짧으면
            if(dp[i][k] <= M){
                sum += item[k];
            }
        }

        if(sum > ans)
            ans = sum;
    }

    cout << ans;

    return 0;
}