[백준 1005] ACM CRAFT

주어진 순서가 있고, 건물마다 걸리는 시간이 있다. 

그럼 순서를 정리하고 목표 건물을 짓기 위해 필요한 다른 건물들의 최대로 걸리는 시간을 목표 건물이 지어지기까지 걸리는 시간에 더하면 되는 것이다.

 

문제에서 들어준 예를 가지고 설명을 해보자면...

목표는 4번. 4번은 2가지의 건물을 지어야만 지어질 수 있다. 그러면 2가지의 건물 중 가장 오래 걸리는 건물의 시간은 3번 100초 이다. 이를 3번과 2번에도 적용하고 쭉쭉해보면 120초라는 걸 알 수 있다.

 

순서 정렬 -> 건물 직전 단계의 건물들의 건설 시간 중 가장 오래 걸리는 걸 택함 <-- 반복 --> 반복해서 시작점까지 왔으면 목표건물의 지어지는 시간 까지 합하면 끝.

 

<소스코드>

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

using namespace std;

int T;
int N, K, Destination;

vector<vector<int> > Push_order;
vector<int> time_sum, time, unit;

int main() {


	cin >> T;
	while (T--) {
		time_sum.clear();
		time.clear();
		unit.clear();
		Push_order.clear();

		cin >> N >> K;

		time_sum.resize(N + 1);
		time.resize(N + 1);
		unit.resize(N + 1);
		Push_order.resize(N + 1);

		for (int i = 1; i < N + 1; i++) {
			cin >> time[i];
		}

		for (int i = 0; i < K; i++) {
			int u, v;
			cin >> u >> v;
			Push_order[u].push_back(v);
			unit[v]++;
		}

		cin >> Destination;

		queue<int> q;

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

		while (!q.empty()) {
			int now = q.front();

			q.pop();

			if (now == Destination) break;

			for (int &next : Push_order[now]) {
				if (--unit[next]== 0)
					q.push(next);

				if (time_sum[next] < time_sum[now] + time[next])
                    time_sum[next] = time_sum[now] + time[next];
			}
		}

		cout << time_sum[Destination] << '\n';
	}
}

위의 소스코드는 https://degurii.tistory.com/17 를 상당히 아주아주 많이많이 참고했다. 감사합니다 (__ __)

끝.