글 읽기 - 재귀적으로 풀었는데 어느부분에서 틀리는지 잘 모르겠습니다.

zxcv551133 5년 전 0

4%즈음 가다가 틀리는걸로 봐서는 경계값 처리가 잘못된 것 같은데

어떤 것인지 모르겠습니다.

의견 주시면 감사하겠습니다.

//https://www.acmicpc.net/problem/2098
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
int n;
int INF = 20000000;
vector<vector<int>> weight(16,vector<int>(16));
vector<vector<int>> memo(1 << 20,vector<int>(16,-1));


int count1 = 0;

int go(int visit, int current, int cost) {
	count1++;
	int &ret = memo[visit][current];
	if (visit>>4 == (1 << n) - 1) {
		return ret = weight[current][visit % 16] == 0 ? INF : cost + weight[current][visit % 16];
	}
	if (ret != -1) {
		return ret;
	}
	ret = INF;
	for (int i = 0; i < n; i++) {
		if (((visit >> 4)&(1 << i)) == 0 && weight[current][i] != 0) {	
			ret = min(ret,go(visit|(1<<i+4), i, cost + weight[current][i]));
		}
	}
	return ret;
}

int main() {
	//freopen("input.txt", "r",stdin);
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> weight[i][j];
		}
	}
	int ans = INF;
	for (int i = 0; i < n; i++) {
		ans = min(ans, go((1 << (i + 4)) + i, i, 0));
	}
	cout << ans << '\n';
	//cout << count1 << '\n';
	return 0;
}

zxcv551133 5년 전 0

해결했습니다. cost 를 추가하면 안되는거였네요.

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

문제

문제

출처

ICPC

재귀적으로 풀었는데 어느부분에서 틀리는지 잘 모르겠습니다.

zxcv551133 5년 전 0

zxcv551133 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말