[BOJ] 1005 : ACM Craft

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

const int n_ = 1e3 + 3;

int req[n_], dst[n_], idg[n_], ans[n_];
vector<int> gph[n_];

void dfs(int now) {
	idg[now]--;
	for (int nxt : gph[now]) {
		ans[nxt] = max(ans[nxt], ans[now] + req[nxt]);
		if (!(--idg[nxt])) dfs(nxt);
	}
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);

	int tc;
	cin >> tc;

	while (tc--) {
		int n, k, w;
		cin >> n >> k;

		for (int i = 0; i <= n; i++) gph[i].resize(0);
		memset(req, 0, sizeof(req));
		memset(idg, 0, sizeof(idg));
		memset(ans, 0, sizeof(ans));
		
		for (int i = 1; i <= n; i++) {
			cin >> req[i];
		}
		for (int i = 0; i < k; i++) {
			int u, v;
			cin >> u >> v;
			gph[u].push_back(v);
			idg[v]++;
		}
		cin >> w;

		for (int i = 1; i <= n; i++) {
			if (!idg[i]) {
				ans[i] = req[i];
				dfs(i);
			}
		}

		cout << ans[w] << "\n";
	}

	return 0;
}