[백준] 1005번 - ACM Craft

백준 1005번 ACM Craft

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

---

코드

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

vector<int> v[1003];
queue<int> q;
int indegree[1003];
int time[1003];
int dp[1003];
int N,M,W;

void init(){
	int mx = 1001;
	for(int i=1;i<=mx;i++){
		dp[i] = time[i] = indegree[i] = 0;
		v[i].clear();
	}
}

int topology(){
	for(int i=1;i<=N;i++){
		if(indegree[i]==0){
			q.push(i);
			dp[i] = time[i];
		}
	}

	while(!q.empty()){
		int cur = q.front();
		q.pop();
		for(int i=0;i<v[cur].size();i++){
			int next = v[cur][i];
			if(dp[next] < dp[cur])
				dp[next] = dp[cur];
			if(--indegree[next]==0){
				q.push(next);
				dp[next] += time[next];
			}
		}
	}
	
	return dp[W];
}

int main(){	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int T;
	cin >> T;
	while(T--){
		init();
		
		cin >> N >> M;
		for(int i=1;i<=N;i++)
			cin >> time[i];
		for(int i=0;i<M;i++){
			int a,b;
			cin >> a >> b;
			v[a].push_back(b);
			indegree[b]++;
		}
		cin >> W;
		
		cout << topology() << '\n';
	}
}

---

풀이

DP와 위상 정렬