[백준] 1005 ACM Craft c++

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

1005번: ACM Craft

 

풀이과정

이 문제는 dp와 위상 정렬을 같이 쓰는 문제이다.  
res배열이 dp이고, 각 지점을 지날 때 가장 오래 걸리는 시간을 넣는 배열이다.

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

int T, N, K, x, y, W;
int build[1001];
int indegree[1001]; // 진입차수
int res[1001];

queue <int> q;
vector <int> v[1001];

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			res[i] = build[i];
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			indegree[next]--;

			res[next] = max(res[next], res[now] + build[next]);
			if (indegree[next] == 0) {
				q.push(next);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> T;
	while (T--) {
		cin >> N >> K;
		for (int i = 1; i <= N; i++) { // 각 건물당 건설 시간
			cin >> build[i];
		}
		for (int i = 0; i < K; i++) { // 건설 순서
			cin >> x >> y;
			v[x].push_back(y);
			indegree[y]++;
		}
		cin >> W;

		topologySort();
		cout << res[W] << "\n";

		memset(build, 0, sizeof(build));
		memset(indegree, 0, sizeof(indegree));
		memset(res, 0, sizeof(res));
		memset(v, 0, sizeof(v));
	}
}