글 읽기 - WA 틀렸습니다

zxcv551133 6년 전 0

어떤점에서 틀리는지 모르겠습니다.

기저설정을 잘못한것 같지는 않은데

WA가 나옵니다.

어느부분이 잘못되었는지 도움주시면 정말감사하겠습니다.

//https://www.acmicpc.net/problem/2098
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

const int INF = 100000000;
vector<vector<int>> ar(16, vector<int>(16));
vector<vector<int>> memo((1 << 20),vector<int>(16,-1));

int n;
int go(int visit, int current, int cost) {
	int &ret = memo[visit][current];
	if (ret != -1)	return ret;
	if((visit >> 4) % (1 << n) + 1 == (1 << n) && ar[current][visit%16]!=0 ) {
		//cout << "current " << current << " start " << visit % 16 << " cost " << cost + ar[current][visit % 16] << '\n';
		return ret = cost + ar[current][visit % 16];
	}
	ret = INF;
	for (int i = 0; i < n; i++) {
		if (visit&(1 << (4 + i))) {
		}
		else {
			if (ar[current][i] != 0) {
				//cout << bitset<8>(visit) << ' ' << bitset<4>(1 << i) << " current " << current << " cost " << cost + ar[current][i] << '\n';
				ret = min(ret, go(visit |= (1 << (4 + i)), i, cost + ar[current][i]));
			}			
		}
	}
	return ret;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ar[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 << ans << '\n';
	return 0;
}

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

문제

문제

출처

ICPC

WA 틀렸습니다

zxcv551133 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말