Boj 1005) Acm Craft

문제

백준 1005

설명

위상정렬을 쓸 수도 있지만 DP 로 풀리는 문제이다. 왜냐하면 순서가 중요한게 아니라 최대 거리만이 중요하기 때문이다.

시간 복잡도

O(\(E\))

코드

int n, k, w;
vector<int> targets[1000];
int dp[1000], d[1000];

int DFS(int cur)
{
	if (dp[cur] >= 0) return dp[cur];
	dp[cur] = 0;
	for (int s : targets[cur]) dp[cur] = max(dp[cur], DFS(s));
	return dp[cur] += d[cur];
}

int main()
{
	fastio;
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n >> k;
		for (int i = 0; i < n; i++) cin >> d[i];
		for (int i = 0; i < k; i++)
		{
			int a, b; // afisrt
			cin >> a >> b;
			targets[--b].push_back(--a);
		}
		cin >> w; w--;

		fill(dp, dp + n, -1);
		cout << DFS(w) << '\n';

		fill(d, d + n, 0);
		for (int i = 0; i <= n; i++) targets[i].clear();	
	}
}