글 읽기 - 1005 ACM craft

bjs1409 9년 전 0

아 반례가 어떤게 있는지 도저히 못찾겠습니다. ㅠㅠ

#include<stdio.h>
#include<vector>
using namespace std;
typedef struct{
	int completeTime;
	vector<int> myVector;
}build;
int result = 0;
void DFS(int fcon, int sum, build* b){
	int fTime = b[fcon].completeTime + sum;
	while (!b[fcon].myVector.empty()){
		int x = b[fcon].myVector.back();
		b[fcon].myVector.pop_back();
		DFS(x, fTime, b);
	}
	if (result < fTime)
		result = fTime;
}
int main(){
//	freopen("input.txt", "r", stdin);
	int testCase; scanf("%d", &testCase);
	int need, vertex;
	while (testCase--){
		build b[1001];
		int numBuilding, techTree, condition;
		scanf("%d %d", &numBuilding, &techTree);
		result = 0;
		for (int i = 1; i <= numBuilding; i++){
			scanf("%d", &b[i].completeTime);
		}
		for (int i = 0; i < techTree; i++){
			scanf("%d %d", &need, &vertex);
			b[vertex].myVector.push_back(need);
		}
		scanf("%d", &condition);
		result = b[condition].completeTime;
		while(!b[condition].myVector.empty()){
			int sum = b[condition].completeTime;
			int x = b[condition].myVector.back();
			b[condition].myVector.pop_back();
			DFS(x, sum, b);
		}
		printf("%d\n", result);
	}
	return 0;
}

baekjoon 9년 전 0

일단 이 문제는 DFS보다 BFS응용을 이용해서 푸는 것이 좋습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1005 ACM craft

bjs1409 9년 전 0

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말