글 읽기 - 시간을 좀더 줄일수는 없을까요.>??

heroswift15 5년 전 0

제가 생각하기에 지금 벡터를 0으로 만들어 주면서 N 번 도는데 너무 시간이 아깝습니다......

위상 정렬을 이용하였습니다. N 번 회전 하는거 말고 다른 방법이 있을까요 ?? ㅠㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int N, K ;
	int detine;  //목적지.
int build[1001];
int inde[1001];
int ans[1001];
	vector<int> a[1001];
	queue<int > q ;

void topsolo()
{
	int i,j;

	
	for(i=1; i<= N ; i++)
		if(inde[i] == 0)
		{
			ans[i] = build[i]; // 기본적을 이 건물을 짓는데 필요한 시간을 저장해준다.
			q.push(i);
		}
	
	
	
	for(i=1; i<=N ; i++)
	{
		int x = q.front();
			q.pop();
		
		for(j= 0 ; j<a[x].size(); j++ )
		{
			int y= a[x][j];
			
			ans[y] = max(ans[y] , ans[x] + build[y]);
			
			if( --inde[y] == 0)
				q.push(y);	
					
		}
		
	}

}


int main()
{
	int i,j;
	int kase;
	
	cin >> kase;
	
	while(kase-- )
	{
		cin >> N >> K; 

			for(i=1; i<=N ; i++)
			cin >> build[i]; 

		
			for(i=1; i<=K ; i++)
			{
				int x, y;

				cin >> x >> y;
				// x를 지은 다음에 y  를 지을수 있다.

				a[x].push_back(y);
				inde[y]++;

			}
		
		cin >> detine;
		
		topsolo();
		
		printf("%d\n",ans[detine]);
		
			for(i=1; i<=N ; i++)
				a[i].clear();
				memset(ans,0,sizeof(ans));
				memset(inde,0,sizeof(inde));
				memset(build,0,sizeof(build));
		
	}
	
	
	
	return 0;
}

yoonsang9114 5년 전 1

함수를 메인으로 넣고 벡터를 메인 안에서 생성하면 어떨까요(...)

seico75 5년 전 1

위분이 말씀하신데로 a 배열을 날리고, 다시 만드는 방향으로 해서

59 ~77 라인을 a 배열 생성과 함께 함수 안에 넣어버리면 clear 는 없어질 것 같습니다.

그런데 백준에서 시간 줄이는 것이 원하시는 바라면

이 문제는 입력이 많아서 아래 부분을 넣는 것이 더 도움이 될 것 같습니다.

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

문제

문제

출처

ICPC

시간을 좀더 줄일수는 없을까요.>??

heroswift15 5년 전 0

yoonsang9114 5년 전 1

seico75 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말