백준 1005 ACM Craft | C++

 

 

 

이번 포스팅은 백준 1005번 ACM Craft입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1005

1005번: ACM Craft

 

 

기본 알고리즘

위상 정렬 Topological Sort

 

풀이

최소 시간을 갱신하는 조건 

line49

result[next] = max(result[next], result[cur] + time[next]); 

 

정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시간을 더한 값이다.

 

 

 

전체 코드

 

//백준1005 ACM Craft                                                        
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    int T;
    cin >> T;
    
    while (T--){
        int N, K;
        cin >> N >> K;
 
        int time[1002];
        for (int i = 1; i <= N; i++) {
            cin >> time[i];
        }
 
        vector<int> adj[1002];
        int inDeg[1002] = { 0, };
        queue<int> q;
        int result[1002];
 
        while (K--) {
            int X, Y;
            cin >> X >> Y;
            adj[X].push_back(Y);
            inDeg[Y]++;
        }
 
        int W;
        cin >> W;
 
        for (int i = 1; i <= N; i++) {
            if (inDeg[i] == 0) {
                q.push(i);
            }
            result[i] = time[i];
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
                inDeg[next]--;
                result[next] = max(result[next], result[cur] + time[next]);
 
                if (inDeg[next] == 0) {
                    q.push(next);
                }
            }
        }
 
        cout << result[W] << endl;
    }
    
    return 0;
}