1516:게임개발하기

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

int N, M;
queue<int>q;
int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	vector<int>indegree;
	vector<int>result;
	vector<int>selfBuild;
	vector<vector<int>>alist;
	
	alist.resize(N + 1);
	indegree.resize(N + 1);
	result.resize(N + 1);
	selfBuild.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> selfBuild[i];
		while (1) {
			int preTemp;
			cin >> preTemp;
			if (preTemp == -1) {
				break;
			}
			alist[i].push_back(preTemp);
			indegree[preTemp]++;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < alist[now].size(); i++) {
			int next = alist[now][i];
			indegree[next]--;
			result[next] = max(result[next], result[now] + selfBuild[now]);
			if (indegree[next] == 0)q.push(next);
		}
	}
	for (int i = 1; i <= N; i++) {
		cout << result[i] + selfBuild[i] << "\n";
	}
	return 0;
}

[출력]