BOJ 1005 : ACM Craft

 

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

문제 요약

정점에 가중치가 있는 방향 그래프가 주어졌을 때, 최초 진입 차수가 0인 정점에서부터 지정된 정점까지 가는 경로의

가중치 합의 최솟값을 구하는 문제이다.

 

접근

기본적인 위상 정렬 문제이다.

 

배열 deg를 선언하여 i번 정점을 자손으로 두는 정점의 개수를 저장한다. 다시 말해, 진입 차수를 나타내는 배열이다.

deg배열과 큐 자료 구조를 이용하여 위상 정렬을 수행한다.
사전에 배열 d를 선언하여 i번 정점까지 지나오면서의 가중치 합의 최솟값을 저장한다.
위상 정렬을 수행하면서 max함수를 통해 d[i]를 계속 갱신시켜주며 문제를 해결할 수 있다.

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--) {
		int N, K, r[1001]{}, a, b, deg[1001]{}, des, d[1001]{};
		vector<vector<int> > V(1001);
		cin >> N >> K;
		for (int i = 1; i <= N; i++)	cin >> r[i];
		while (K--) {
			cin >> a >> b;
			V[a].push_back(b);
			deg[b]++;
		}
		cin >> des;

		queue<int> Q;
		for (int i = 1; i <= N; i++)
			if (!deg[i]) {
				Q.push(i);
				d[i] = r[i];
			}
		for (int i = 1; i <= N; i++) {
			int now = Q.front();
			Q.pop();
			for (int j : V[now]) {
				d[j] = max(d[j], d[now] + r[j]);
				if (!(--deg[j])) {
					Q.push(j);
				}
			}
		}
		cout << d[des] << '\n';
	}
}