[BOJ 1005] ACM Craft

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

1005번: ACM Craft

---

위 문제는 [BOJ 1516] 게임 개발 와 거의 유사한 문제이다. 똑같이 위상정렬을 통해 건물이 지어지는 시간을 갱신하여 출력하면 된다.

 

ACM Craft는 1516번 문제와는 다르게 1개의 건물만 출력하면 되기 때문에 그 부분만 수정하면 된다.

---

#include <stdio.h>
#include <vector>
#include <queue>

#define max(a, b) ((a) > (b) ? (a) :(b))

using namespace std;

int n, k, w;
int time[1001];
int indgree[1001];
int ans[1001];

int main()
{

	int T;
	scanf("%d", &T);
	while (T--)
	{
		vector<vector<int>> g;
		scanf("%d%d", &n, &k);
		g.resize(n + 1);
		for (int i = 1; i <= n; i++)
			scanf("%d", time + i);

		for (int i = 0; i < k; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);

			g[x].push_back(y);
			indgree[y]++;
		}
		scanf("%d", &w);

		queue<int> q;

		for (int i = 1; i <= n; i++)
		{
			if (indgree[i] == 0)
				q.push(i);
			ans[i] = time[i];
		}

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

			for (auto s = g[p].begin(); s != g[p].end(); s++)
			{
				if (--indgree[*s] == 0)
					q.push(*s);

				ans[*s] = max(ans[*s], ans[p] + time[*s]);
			}
		}

		printf("%d\n", ans[w]);
	}
}