白駿1005 ACM Craft

白駿1005 ACM Craft

リンク:https://www.acmicpc.net/problem/1005

質問する

キー(Key)

◆位相ソートにより、特定の建築xを建造するための先行建築経路のうち、最長時間の経路の時間をtotatime[x]に入れる.
建物を建てることができる場合(indgree[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';

	}
}

追加

以前に解決したタイプの問題だったので、スムーズに解決できました.