글 읽기 - 시간초과

heroswift15 4년 전 0

플로이드와 DFS 를 이용하였습니다. 하지마 시간초과.....

극복 할수있는 방법 있을까요?? ㅠㅠ

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

int map[401][401];
vector<int > tt;
vector<pair<int ,int > >as[401];
int ans = 987654321;

int visited[401];






void dfs(int x , int des , int cnt ,int cost)
{
	int i;

	if(cnt == tt.size())
	{	
		ans = -1;
		return;
	}

	if(des == x &&  cnt != 0 )
	{

	//	printf("%d    cost : [%d]   cnt : [%d] \n", des ,cost ,cnt);
		if( ans > cost)
		ans = cost ;
		return;
	}
		
	for( i = 0 ; i < as[x].size(); i++)
	{

		int nextcost = as[x][i].first;
		int next = as[x][i].second;
	//	printf("nextcost : [%d] \n" ,nextcost);

		if(visited[next]) continue;

			visited[next] = 1;

			dfs( next , des , cnt + 1 , cost + nextcost);

			visited[next] = 0;


	}


}


int main()
{

		int i,j,k;
		int V , E;
		scanf("%d%d" , & V , &E);
	
		for( i = 1 ; i <= V ; i++ )
		for( j = 1 ; j <= V ; j++ )
		map[i][j] = 20001;





	int a,b,c;
	for( i =1; i <=E ; i++) {
		scanf("%d%d%d", &a, &b, &c );
		map[a][b] = c;

	}


	for( k = 1 ; k <= V ; k++ )
	for( i = 1 ; i <= V ; i++ )
	for( j = 1 ; j <= V ; j++ )
	{

			if( i == j || j==k || i == k) continue;

			if(map[i][j] > map[i][k] + map[k][j])
			 map[i][j] = map[i][k] + map[k][j] ;
	}


	for( i = 1 ; i <= V ; i++ )
	for( j = 1 ; j <= V ; j++ )
	{
		if( i == j || j==k || i == k) continue;

		if(map[i][j] == 20001 ) continue;

		//printf("map[%d][%d]  : %d\n" , i,j,map[i][j] );
		as[i].push_back( make_pair( map[i][j] , j ));

		tt.push_back(i);

	}

	for( i = 0 ; i < tt.size(); i++ )
	{
		
		memset(visited , 0 ,sizeof( visited));

		//visited[tt[i]] =1;
		dfs(tt[i] , tt[i] , 0 , 0);
		//visited[tt[i]] = 0;
	}



	printf("%d", ans);


	return 0;
}

heroswift15 4년 전 0

a미궁속으로 가버리는길 ~ ^^

sait2000 4년 전 1

dfs를 왜 돌리세요? 플로이드를 마치고 나면 `map[i][i]`에 들어가는게 i에서 출발해서 i로 끝나는 사이클의 최소 길이인데요.

heroswift15 4년 전 0

에궁 나는 멍뚱이; ㅜㅜ 감사합니다

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

문제

문제

출처

ICPC

시간초과

heroswift15 4년 전 0

heroswift15 4년 전 0

sait2000 4년 전 1

heroswift15 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말