[백준/C++] 1005 ACM Craft

1005 ACM Craft

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

1005번: ACM Craft

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

int t,n,k,w;
int main()
{
	cin >> t;
	for (int i = 0; i < t; ++i)
	{
		int time_table[1002];
		int result[1002];
		int indegree[1002] = { 0, };
		vector<int> adj[1002];
		queue<int> q;
		
		cin >> n >> k;
		for (int j = 1; j <= n; ++j)
		{
			cin >> time_table[j];
		}

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

		for (int j = 1; j <= n; ++j)
		{
			if (indegree[j] == 0)
				q.push(j);
			result[j] = time_table[j];
		}

		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			for (int j = 0; j < adj[x].size(); ++j)
			{
				int y = adj[x][j];
				--indegree[y];
				result[y] = max(result[y], result[x] + time_table[y]);
				if (0 == indegree[y])
					q.push(y);
			}
		}
		cout << result[w] << "\\n";
	}
	return 0;
}

• 위상정렬 문제
• w를 건설하기 위해서는 w하위에 연결된 모든 건물이 완료되어야 하기 떄문에, w까지 연결되는 여러 경로 중 소요되는 시간이 최대일 때와 같다.