백준 1005 ACM Craft

백준 1005 ACM Craft

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

문제

키 포인트

◆ 위상 정렬을 통해 특정 건물 x를 짓기 위한 선행건물 루트중에 가장 시간이 오래걸리는 루트의 시간을 totaltime[x] 에 넣어줌.
해당 건물을 지을 수 있게되면 (indegree[x] 값이 0이되면) 해당 건물을 짓는 시간(times[x])을 더해줌

시행착오

없었음

코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
    //times : 각 단일 건물들을 짓는데 걸리는 시간
    //toaltimes : 해당 건물을 짓기위해 걸리는 총 시간
    		int n, k, times[1001], indegree[1001], w, totaltime[1001];
		vector<int> order[1001];
		queue<int> q;
		cin >> n >> k;
		fill(indegree, indegree + n + 1, 0);
		fill(totaltime, totaltime + n + 1, 0);


		for (int j = 1; j <= n; j++) cin >> times[j];
		for (int j = 0; j < k; j++) {
			int x, y;
			cin >> x >> y;
			indegree[y]++;
			order[x].push_back(y);
		}
		cin >> w;

		for (int j = 1; j <= n; j++) 
			if (indegree[j] == 0) {
				q.push(j);
				totaltime[j] = times[j];
			}

		while (!q.empty()) {
			int sz = q.size();
			for (int j = 0; j < sz; j++) {
				int x = q.front();
				q.pop();

				for (int k = 0; k < order[x].size(); k++) {
					totaltime[order[x][k]] = max(totaltime[order[x][k]], totaltime[x]);
					if (--indegree[order[x][k]] == 0) {
						q.push(order[x][k]);
						totaltime[order[x][k]] += times[order[x][k]];
					}

				}
			}
		}
		cout << totaltime[w] << '\n';

	}
}

추가

예전에 풀어봤던 유형의 문제라 무난하게 해결했다.