BOJ-1516-게임 개발

[changicho]

문제번호. 문제 제목

링크

난이도	정답률(_%)
Gold II	46

설계

위상정렬

정리

내 코드	빠른 코드
4 ms

고생한 점

code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

void solution() {
	int N;
	cin >> N;

	vector<int> answers(N + 1, 0);
	vector<int> costs(N + 1);
	vector<vector<int> > graph(N + 1);
	vector<int> indegree(N + 1, 0);

	for (int i = 1; i <= N; i++) {
		int time, cur = 0;
		cin >> time;
		costs[i] = time;

		while (cin >> cur, cur!=-1) {
			graph[cur].push_back(i);
			indegree[i] += 1;
		}

	}

	queue<int> q;

	// find the roots
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			answers[i] = costs[i];
		}
	}

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

		for (int next : graph[cur]) {
			answers[next] = max(answers[next], answers[cur] + costs[next]);

			indegree[next] -= 1;
			if (indegree[next] == 0) q.push(next);
		}
	}

	for (int i = 1; i < answers.size();i++) {
		cout << answers[i] << "\n";
	}
}

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

	solution();

	return 0;
}