글 읽기 - [1005] DFS 반례를 못찾겠습니다....질문드립니다 ㅠㅠ

sukth09 5년 전 0

질문게시판에있는 대부분 테스트케이스를 해보았는데 다 답이나왔습니다 ㅠㅠ

건물이 하나일 수도 있나요??

아니면 알고리즘이 잘못되었나요??

dfs로는 풀지 못하나요??ㅠㅠㅠㅠ

//#define TEST_CASE

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define MAX 1000

int T, N, K, X, Y, W;
unsigned int D[MAX + 1];
unsigned int dp[MAX + 1];
vector<int> v[MAX + 1];

unsigned int dfs(int w) {
	unsigned int max = 0;

	if(dp[w]) {
		return dp[w];
	}

	while(v[w].size()) {
		unsigned int tmp = dfs(v[w].back());
		max = max < tmp ? tmp : max;
		v[w].pop_back();
	}
	dp[w] = D[w] + max;
	return dp[w];
}

int main() {
	#ifdef TEST_CASE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	scanf("%d", &T);
	for(int i = 0; i < T; i++) {
		unsigned int res;
		memset(D, 0, MAX + 1);
		memset(dp, 0, MAX + 1);
		for(int j = 0; j < MAX + 1; j++)
			v[j].clear();

		scanf("%d %d", &N, &K);

		for(int j = 1; j <= N; j++)
			scanf("%d", &D[j]);

		for(int j = 0; j < K; j++) {
			scanf("%d %d", &X, &Y);
			v[Y].push_back(X);
		}
		scanf("%d", &W);
		res = dfs(W);
		printf("%d\n", res);
	}

	#ifdef TEST_CASE
	fclose(stdin);
	fclose(stdout);
	#endif

	return 0;
}