[BOJ] 1005 : ACM Craft - travelbeeee

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

---

위상정렬

위상정렬 문제로 endNode 까지 도착하는데 가장 긴 경로를 구하면 된다.

자세한 풀이는 BOJ 1516 게임 개발 풀이를 참고해주시면 감사합니다. 

(https://travelbeeee.tistory.com/375)

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

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

	int t;
	cin >> t;
	while(t--){
		int N, K, endGame, time[1001] = {}, inDegree[1001] = {}, ans[1001] = {};
		vector<int> graph[1001];
		stack<int> s;

		cin >> N >> K;
		for (int i = 1; i <= N; i++)
			cin >> time[i];
		for (int i = 0, x, y; i < K; i++) {
			cin >> x >> y;
			graph[x].push_back(y);
			inDegree[y]++;
		}
		cin >> endGame;

		for (int i = 1; i <= N; i++)
			if (inDegree[i] == 0){
				s.push(i);
				ans[i] = time[i];
			}

		while (!s.empty()) {
			int cur = s.top();
			s.pop();
			if (cur == endGame) {
				cout << ans[cur] << '\n';
				break;
			}
			for (int i = 0; i < graph[cur].size(); i++) {
				inDegree[graph[cur][i]]--;
				ans[graph[cur][i]] = max(ans[graph[cur][i]], ans[cur] + time[graph[cur][i]]);
				if (inDegree[graph[cur][i]] == 0) {
					s.push(graph[cur][i]);
				}
			}
		}
	}
	return 0;
}

---