글 읽기 - 1005번 질문 드립니다

barcelonamessi 10년 전 0

현재 건물의 시간을 알려면 이전 건물 완성시간중 가장 느린거에다가 현재 건물 시간 더한거라고 생각하고

재귀함수를 이용했는데 시간 초과가 발생했네요

재귀함수를 쓴것이 문제인가요??

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

int vertex[1024];
//int edge[1024][1024];
int n;
vector<int> edge[1024];



int dfs(int num)
{
	//종료 조건 알아내고
	int i;
	bool is_found=false;
	int D;
    if(edge[num].size()==0)
        return vertex[num];

	for(i=0; i<edge[num].size(); i++) //해당하는 것 있으면 가봄 이들중에서 가장 큰 값에서 현재 값을 더해야함
	{
		int temp=dfs(edge[num][i]); //일단 찾아봄
		
		
		if(!is_found) //처음이면 일단 저장
		{
			is_found=true;
			D=temp;
		}
		else //두번째 이상이면 더 큰 값을 저장해야함
		{
			if(temp>D)
				D=temp;
					
		}

		
	}
	
		return vertex[num]+D;

	


}

int main(void)
{

	int test;
	int i,j;
	scanf("%d", &test);

	while(test--)
	{
		int m;
		int first, second;
		int result;
		int num;
		scanf("%d %d", &n, &m);

		memset(vertex, 0, sizeof(int)*1024);
		for(i=0; i<=n; i++)
			edge[i].clear();
		

		for(i=1; i<=n; i++)
			scanf("%d", &vertex[i]); //각 지점마다 얼마나 걸리는지 저장

		for(i=0; i<m; i++) //각 연결선마다 가중치를 저장해놓음
		{
			
			
			scanf("%d %d", &first, &second);
			edge[second].push_back(first);
			
			

		}

		scanf("%d", &num);

		result=dfs(num);
		
		//입력완료
		printf("%d\n", result);



	}

	return 0;
}

baekjoon 10년 전 3

네

barcelonamessi 10년 전 0

겨우 풀었네요 ㅜㅜ

30번 시도해서 맞춘건 함정.. 다른분들 풀이보니 신기하네요

답변 감사합니다!!

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

문제

문제

출처

ICPC

1005번 질문 드립니다

barcelonamessi 10년 전 0

baekjoon 10년 전 3

barcelonamessi 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말