0. 문제

문제 링크

1. 풀이

이전에 살펴본 문제 - ACM Craft와 같은 위상 정렬 문제이다.

수행해야 할 작업 $N(1 \leq N \leq 10000)$개가 주어지고, 각각의 작업마다 걸리는 시간이 정수로 주어질 때, 모든 작업을 완료하는 시간을 구하는 문제인데 어떠한 작업들은 앞서 끝내야만 시작할 수 있는 작업이 존재하고, 친절하게도 선행 작업들은 해당 작업보다 작업 번호가 낮다.


즉, $X$번째 작업의 선행 작업의 번호는 $[1 , X-1]$의 범위 안에만 존재한다는 뜻이다.


또한, 별도의 선행 작업 없이 바로 시작할 수 있는 작업들도 존재하며, 특히 1번 작업은 항상 그러하다.


따라서 (1)각 작업들의 선행/후행 구조를 방향그래프로 표현한 후 (2)선행 정점이 없는 정점들을 기준으로 탐색을 수행하며 작업 종료 시간을 갱신해 주고 (3)모든 작업들의 종료 시간을 파악해 가장 늦게 끝나는 작업의 종료 시간을 출력하면 그 시간이 모든 작업이 끝나는 시간(정답)이 된다.

2. 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

constexpr int MAXN = 10001;

vector<int> v[MAXN];
int cost[MAXN];
int d[MAXN];
int pre[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "r", stdin);
	
	queue<int> q;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int preCnt;
		cin >> cost[i] >> pre[i];
		if (pre[i])
		{
			for (int j = 0; j < pre[i]; j++)
			{
				int p;
				cin >> p;
				v[p].push_back(i);
			}
		}
		else
		{
			q.push(i);
			d[i] = cost[i];
		}
	}
	
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i = 0; i < v[cur].size(); i++)
		{
			int next = v[cur][i];
			if (d[next] < cost[next] + d[cur])
			{
				d[next] = cost[next] + d[cur];
				q.push(next);
			}
		}
	}
	cout << *max_element(d + 1, d + n + 1);
	
	return 0;
}

3. 결과