글 읽기 - 시간초과가 나는데...

poia0304 8년 전 0

시간초과가 나는데 더 이상 모르겠어서 잘 아시는 분들이 가르쳐주시면 감사하겠습니다.

나름 dp로 푼거 같은데 16개 예제 넣어보니깐 시간초과가 나네요...ㅠ

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <climits>

using namespace std;

int map[20][20];
int dp[20][0x10000];
int times;

int tsp(int next,int flag)
{
	int m = INT_MAX;

	if (flag == 0) {
		return dp[next][0];
	}

	for (int i = 1; i <= times; ++i) {
		if (flag & (0x01 << i - 1)) { // 0이면 방문 ㄴㄴ
			dp[next][i] = map[next][i] + tsp(i, flag & ~(0x01 << i - 1));
			m = min(dp[next][i],m);
		}
	}

	return m;
}

int main()
{
	int m = INT_MAX;
	int flag = 0;

	scanf("%d",&times);
	
	for (int i = 0; i < times; ++i) {
		flag = flag | (0x01 << i); //도시 표시 ex)4개도시 1111
	}

	for (int i = 1; i <= times; ++i) {
		for (int j = 1; j <= times; ++j) {
			scanf("%d",&map[i][j]);
			if (i != j && map[i][j] == 0) {
				map[i][j] = 1000002;
			}
		}
	}

	for (int i = 1; i <= times; ++i) {
		for (int j = 1; j <= times; ++j) {
			dp[j][0] = map[j][i];
		}
		dp[i][flag] = tsp(i,flag & ~(0x01 << i-1)); //출발도시, 출발도시를 제외한 방문안한 도시표시
		m = min(m,dp[i][flag]);
	}
	printf("%d",m);

	return 0;
}

yukariko 8년 전 0

dp는 중복된 계산을 반복하지 않기 위한 테크닉인데

위 코드엔 그런부분이 없는것같네요

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

문제

문제

출처

ICPC

시간초과가 나는데...

poia0304 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말