딩코딩 : Computer Science 블로그

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

#include <bits/stdc++.h>
using namespace std;

int d[1001];
vector<int> adj[1001];
int degree[1001];
int res[1001];

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

    for (int T = 0; T < t; T++) {
        int n, k;
        cin >> n >> k;
        memset(degree, 0, sizeof(degree));
        memset(res, 0, sizeof(res));
        memset(d, 0, sizeof(d));
        for (int i = 0; i < 1001; i++) adj[i].clear();


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

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            degree[b]++;
        }
        int w;
        cin >> w;

        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
                res[i] = d[i];
            }
        }

        while (!Q.empty()) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                res[nx] = max(res[nx], res[x] + d[nx]);
                if (--degree[nx] == 0) {
                    Q.push(nx);
                }
            }

        }


        cout << res[w] << '\n';



    }


    return 0;
}