BOJ 1005 - ACM 크래프트 (위상정렬)

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

1005번: ACM Craft

 

주석에 중요문장이라고 표시한 문장이 다른 곳에서도 종종 쓰인다.

 

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

int main() {
	int tc; cin >> tc;

	while (tc--) {
		int n, k; cin >> n >> k;
		int w[1001], ind[1001], time[1001];
		for (int i = 0; i < n; i++) {
			cin >> w[i];
			time[i] = w[i];
			ind[i] = 0;
		}
		vector<vector<int>> adj(n);
		for (int i = 0,u,v; i < k; i++) {
			cin >> u >> v;
			adj[u - 1].push_back(v - 1);
			ind[v - 1]++;
		}
		int target; cin >> target;

		queue<int> q;
		for (int i = 0; i < n; i++) if (ind[i] == 0) q.push(i);

		while (!q.empty()) {
			int curr = q.front();
			q.pop();
			for (int next : adj[curr]) {
            		//@중요문장@
				time[next] = max(time[next], time[curr] + w[next]);
				if (--ind[next] == 0) q.push(next);
			}
		}

		cout << time[target-1] << '\n';
	}
	
}