백준 1005번: ACM Craft (C++)

문제 링크 : www.acmicpc.net/problem/1005

 

 

위상정렬과 dp를 이용한 문제이다.

 

위상정렬 알고리즘  :  wlshddlek.tistory.com/39?category=887828

 

<전체적인 알고리즘>

1. 위상정렬 알고리즘으로 순서대로 건물을 짓는다.

   1-1. 건물을 탐색할 때 마다 더 오래 걸리는 시간으로 갱신해준다.

 

 

<전체 코드>

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int time[1002];
vector<int> a[1002];
int indegree[1002];//
int d[1002];//
int n,w;

void topology()
{
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
		{
			q.push(i);    //시작 노드들 넣어주기
			d[i] = time[i];
		}
	}

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

		if (w == node)break;    //결과가 w의 시간을 원하니 w이후로는 볼 필요가 없다.

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i];
			indegree[next]--;
			if (d[next] < time[next] + d[node])d[next] = time[next] + d[node];
			// 이 경로가 시간이 더 길면 시간 갱신

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

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

	int test;
	cin >> test;
	for (int t = 0; t < test; t++)
	{
		int  k;
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
		{
			int num;
			cin >> num;
			time[i] = num;
		}
		for (int i = 0; i < k; i++)
		{
			int n1, n2;
			cin >> n1 >> n2;
			a[n1].push_back(n2);
			indegree[n2]++;
		}
	
		cin >> w;
		
		topology();  //위상정렬
		cout << d[w]<<"\n";

		//리셋 부분
		fill(&d[0], &d[n+1], 0);
		fill(&indegree[0], &indegree[n + 1], 0);
		for (int i = 1; i <= n; i++)a[i].clear();
	}
	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.