코드 복사/붙여넣기 하는 당신이 아름답습니다.

1005 : ACM Craft

풀이

위상딱 위상딱 신나는 노래

나도 한 번 불러본다~

코드

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

const int n_ = 1e3 + 3;

int req[n_], dst[n_], idg[n_], ans[n_];
vector<int> gph[n_];

void dfs(int now) {
	idg[now]--;
	for (int nxt : gph[now]) {
		ans[nxt] = max(ans[nxt], ans[now] + req[nxt]);
		if (!(--idg[nxt])) dfs(nxt);
	}
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		int n, k, w;
		cin >> n >> k;

		for (int i = 0; i <= n; i++) gph[i].resize(0);
		memset(req, 0, sizeof(req));
		memset(idg, 0, sizeof(idg));
		memset(ans, 0, sizeof(ans));
		
		for (int i = 1; i <= n; i++) {
			cin >> req[i];
		}
		for (int i = 0; i < k; i++) {
			int u, v;
			cin >> u >> v;
			gph[u].push_back(v);
			idg[v]++;
		}
		cin >> w;

		for (int i = 1; i <= n; i++) {
			if (!idg[i]) {
				ans[i] = req[i];
				dfs(i);
			}
		}

		cout << ans[w] << "\n";
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-12-29 11:18

Read more posts by this author