[백준] 1005번 ACM Craft

[적용한 알고리즘]

위상정렬

 

[아이디어]

위상정렬

 

[생각의 흐름 / 절차] 

 

 

[교훈]

기본 문제였다

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 1001;

int main(){
    int t; scanf("%d", &t);

    while (t--){
        int N, K;
        int indegree[MAX_N] = { 0 };
        int time[MAX_N] = { 0 };
        vector<int> adj[MAX_N];

        scanf("%d %d", &N, &K);

        for (int i = 1; i <= N; i++){
            scanf("%d", &time[i]);
        }

        for (int i = 0; i < K; i++){
            int from, to;
            scanf("%d %d", &from, &to);

            adj[from].push_back(to);
            indegree[to]++;
        }

        int W; scanf("%d", &W);

        int result[MAX_N] = { 0 };
        queue<int> Q;

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

        for (int i = 1; i <= N; i++){
            int cur = Q.front();
            Q.pop();

            for (int nxt : adj[cur]){
                result[nxt] = max(result[nxt], result[cur] + time[nxt]);
                if (--indegree[nxt] == 0){
                    Q.push(nxt);
                }
            }
        }

        printf("%d\n", result[W]);
    }
    return 0;
}