글 읽기 - 뭐가 틀렸을까요..

kokoxg2 6년 전 0

하..다른 소스랑 비교해도 뭐가 틀린지 이해를 못하겠어요..

#include <cstdio>
#include <cstring>
#include <climits>
#define min(a,b) (a < b ? a : b)
const int IMPOSSIBLE = 1000000000;

int cost_table[10][10], dp[10][1 << 10], city_num;

// a = a | ( 1 << n ) : a변수의 n번째 비트를 켠다.
// a & ( 1 << n ) : n번째 비트가 켜져있는지 확인. ( 켜져있으면 return 1, 꺼진 상태면 return 0 )
// a = a - ( 1<< n ) : a변수의 n번째 비트를 끈다. ( 켜져있을 때만 사용 )
// a = a & ~( 1 << n ) : a변수의 n번째 비트를 끈다. 꺼진 상태면 그대로 유지
// a = a ^ ~( 1 << n ) : a변수의 n번째 비트를 토글한다.

int TSP(int cur, int isVist);

int main() {

	scanf("%d", &city_num);

	for (int i = 0; i < city_num; ++i) 
		for (int j = 0; j < city_num; ++j) 
			scanf("%d", &cost_table[i][j]);
		
	memset(dp, -1, sizeof(dp));

	printf("%d\n", TSP(0, 1));
	return 0;
}

int TSP(int cur, int isVisit) {

	int &ret = dp[cur][isVisit];

	if (ret != -1) return ret;

	if (isVisit == (1 << city_num) - 1) {
		if (cost_table[cur][0] != 0) return cost_table[cur][0];
		return IMPOSSIBLE;
	}

	ret = IMPOSSIBLE;

	for (int i = 0; i < city_num; ++i) {
		// 이미 방문하거나 연결이 안된 도시는 PASS
		if (isVisit & (1 << i) || cost_table[cur][i] == 0) continue;
		
		//int temp = TSP(i,isVisit | (1 << i)) + cost_table[cur][i];
		ret = min(ret, TSP(i, isVisit | (1 << i))) + cost_table[cur][i];
	}

	return ret;
}

kokoxg2 6년 전 0

아 제가 잘못생각했네요

ret = min(ret, TSP(i, isVisit | (1 << i))) + cost_table[cur][i];

랑

ret = min(ret, TSP(i, isVisit | (1 << i))+ cost_table[cur][i]);

가 같은 결과를 낸다고 생각했는데 틀린 생각이었네요.

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

문제

문제

출처

ICPC

뭐가 틀렸을까요..

kokoxg2 6년 전 0

kokoxg2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말