[백준 1005] ACM craft

처음에 단순 BFS로 풀었는데 터졌다.

위상정렬을 써야 한다고 한다.

#include <iostream>
#include <algorithm>
#include <vector>
#define n_ 1000+5
using namespace std;
 
vector<int> v[n_];
int arr[n_];
int ans[n_];
int cnt[n_];
 
void solve(int now){
    cnt[now]--;
 
    for (int i : v[now]){
        ans[i] = max(ans[i], ans[now] + arr[now]);
        cnt[i]--;
        if (!cnt[i]){
            solve(i);
        }
    }
}
 
int main(void){
    int T;
 
    cin >> T;
    while (T--){
        int n, k,w;
 
        cin >> n >> k;
        for (int i = 1; i <= n; i++){
            cin >> arr[i];
            v[i].clear();
            ans[i] = 0;
            cnt[i] = 0;
        }
        for (int j = 0; j < k; j++){
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            cnt[b]++;
        }
        cin >> w;
 
        for (int i = 1; i <= n; i++){
            if (!cnt[i]){
                solve(i);
            }
        }
 
        cout << ans[w] + arr[w] << endl;
    }
}