[백준/BOJ] 백준 1005번 : ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

vector<int> install_time(1001)에 건설에 걸리는 시간 저장하고, vector<int> pre_install[1001]에 해당 건물을 건설하기 위해 그전에 건설해야 될 건물들을 저장한다. 시간을 계산할 때 건물 건설을 위해 시간이 가장 오래 걸리는 이전 건물을 고려한다.

 

코드

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

int tc;
int n, k;
int d;
int x, y;
int w;

vector<int> cache(1001);
vector<int> install_time(1001); //건설에 걸리는 시간 저장
vector<int> pre_install[1001]; //해당 건물을 건설하기 위해 그 전에 건설해야 될 건물들 저장

void Pre()
{
	for (int i = 0; i < 1001; i++)
	{
		cache[i] = -1;
		install_time[i] = 0;
		pre_install[i].clear();
	}
}

int Solve(int building)
{
	int& ret = cache[building];

	if (ret != -1)
		return ret;

	ret = install_time[building];

	for (int i = 0; i < pre_install[building].size(); i++)
	{
		ret = max(ret, install_time[building] + Solve(pre_install[building][i])); //건물 건설을 위해 시간이 가장 오래 걸리는 이전 건물을 고려한다.
	}

	return ret;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n >> k;

		for (int i = 1; i <= n; i++)
		{
			cin >> d;
			install_time[i] = d;
		}

		for (int i = 0; i < k; i++)
		{
			cin >> x >> y;

			pre_install[y].push_back(x); //x를 지은 다음에 건물 y를 지어야 된다
		}

		cin >> w;

		cout << Solve(w) << "\n";
	}

	return 0;
}