[골3] 1005 - ACM Craft

#include <iostream>
#include <vector>
#include <queue>

#pragma region 입출력 속도향상

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

using namespace std;

#define MAX 1002

int main()
{
	FAST_IO();

	int t;
	cin >> t;

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

		int time[MAX];

		for (int i = 1; i <= n; i++)
			cin >> time[i];

		vector<int> adj[MAX];
		queue<int> q;
		int degree[MAX]{ 0 };
		int res[MAX]{ 0 };

		while (k--)
		{
			int x, y;
			cin >> x >> y;
			adj[x].push_back(y);
			degree[y]++;
		}
		int w;
		cin >> w;

		for (int i = 1; i <= n; i++)
		{
			if (degree[i] == 0)
				q.push(i);

			res[i] = time[i];
		}

		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			for (int i = 0; i < adj[cur].size(); i++)
			{
				int nxt = adj[cur][i];
				res[nxt] = max(res[nxt], res[cur] + time[nxt]);
				
				if (--degree[nxt] == 0)
					q.push(nxt);
			}
		}
		cout << res[w] << '\n';
	}
	return 0;
}