Skip to content

BOJ-1516-게임 개발 #54

Open
Open

Description

@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;
}

Activity

  1. added this to the day6 milestone on Jan 13, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    clear정답코드

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions