1005 ACM Craft

 

1005번: ACM Craft

 

 

DP라기 보다는 위상 정렬에 더 무게를 둔 문제이다.

각 건물의 선행 건물들과 선행 건물의 수를 그 건물에 대응되는 배열의 위치에 저장한 후

큐를 이용하여 건물들을 짓는 것에 조건을 만족하며 소요되는 최소 시간을 계산하는 방식으로 해결하였다.

 

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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	
	for (int i = 0; i < t; ++i) {
		int n, k;
		cin >> n >> k;

		vector<int> time(n);
		for (int j = 0; j < n; ++j) {
			cin >> time[j];
		}

		vector<vector<int>> pres(n);
		vector<int> pres_cnt(n);
		int x, y, w;
		for (int j = 0; j < k; ++j) {
			cin >> x >> y;
			pres[x - 1].push_back(y - 1);
			++pres_cnt[y - 1];
		}
		cin >> w;
		w -= 1;

		queue<int> q;

		for (int j = 0; j < n; ++j) {
			if (pres_cnt[j] == 0) {
				q.push(j);
			}
		}

		vector<int> cost(n);

		while (pres_cnt[w] > 0) {
			int f = q.front();
			q.pop();

			for (auto b : pres[f]) {
				cost[b] = max(cost[b], cost[f] + time[f]);
				--pres_cnt[b];
				if (pres_cnt[b] == 0) {
					q.push(b);
				}
			}
		}

		cout << cost[w] + time[w] << '\n';
	}
	return 0;
}