백준 1516번 게임 개발

문제 링크입니다: https://www.acmicpc.net/problem/1516

1516번: 게임 개발

간단한 위상정렬 문제였습니다.

핵심은 max(result[nextNode], result[node] + duration[node]); 이 부분이였습니다.

 

	#include <iostream>
	#include <vector>
	#include <queue>
	using namespace std;
	const int MAX = 500 + 1;
	int N;
	int inDegree[MAX];
	int duration[MAX];
	int result[MAX];
	vector<int> graph[MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
	int time;
	cin >> time;
	duration[i] = time;
	while (1)
	{
	int node;
	cin >> node;
	if (node == -1)
	{
	break;
	}
	inDegree[i]++;
	graph[node].push_back(i);
	}
	}
	queue<int> q;
	for (int i = 1; i <= N; i++)
	{
	if (inDegree[i] == 0)
	{
	q.push(i);
	}
	}
	while (!q.empty())
	{
	int node = q.front();
	q.pop();
	for (int i = 0; i < graph[node].size(); i++)
	{
	int nextNode = graph[node][i];
	result[nextNode] = max(result[nextNode], result[node] + duration[node]);
	if (--inDegree[nextNode] == 0)
	{
	q.push(nextNode);
	}
	}
	}
	for (int i = 1; i <= N; i++)
	{
	cout << result[i] + duration[i] << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~