BOJ 1005 ACM Craft

ACM Craft [골드3]

---

문제 링크

https://www.acmicpc.net/problem/1005

풀이

건물마다 선행되어야 하는 건설 순서를 위상정렬에 따라 시간을 계산하여 저장한 뒤, 정답 건물에 해당하는 건설 시간의 합을 출력한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int T, N, K, X, Y, W;
int D[1001], indegree[1001];
vector<int> adj[1001];
int answer[1001];

queue<int> q;

int main(void)
{
    cin >> T;

    for (int t = 1; t <= T; t++)
    {
        fill_n(&D[0], 1001, 0);
        fill_n(&indegree[0], 1001, 0);
        fill_n(&answer[0], 1001, 0);
        for (int i = 0; i <= 1000; i++) {
            adj[i].clear();
        }

            cin >> N; // 건물 갯수
        cin >> K; // 건설 순서 규칙 갯수

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

        for (int i = 1; i <= K; i++)
        {
            cin >> X >> Y;
            adj[X].push_back(Y);
            indegree[Y]++;
        }

        cin >> W;

        for (int i = 1; i <= N; i++)
        {
            if (indegree[i] == 0)
            {
                q.push(i);
            }
        }

        while(!q.empty())
        {
            int elem = q.front();
            q.pop();

            for (int i = 0; i < adj[elem].size(); i++)
            {
                int next = adj[elem].at(i);
                answer[next] = max(answer[next], answer[elem] + D[next]);

                indegree[next]--;

                if(indegree[next] == 0) {
                    q.push(next);
                }
            }
        }


        cout << answer[W] << "\n";
    }

    return 0;
}