글 읽기 - 반례가 궁금합니다.

melon940925 3년 전 0

현재위치와 이전위치, 그리고 여태방문한 위치들(비트마스크)로 dp배열을 만들어서 풀었는데요!

6%에서 계속 틀리네요 ..

질문 게시판에 있는 반례들은 모두 맞습니다.

무엇이 문제일까요?

#include <bits/stdc++.h>
#define endl '\n'
#define F(i,n) for(int i=1; i<=n; i++)
using namespace std;
int arr[17][17];
int dp[17][17][1 << 15 + 1];
int N;
int MAX;
int MAXIMUM;

int DFS(int now, int prev, int visit, int first) {
	if (visit == MAX) {
		if (!arr[now][first])return 1e9;
		return arr[now][first];
	}
	int& ret = dp[now][prev][visit];
	if (ret != MAXIMUM)return ret;

	F(i, N) {
		if (i != now && i != prev && !(visit & (1 << (i - 1)))) {
			if (visit == 0) {
				ret = min(ret, DFS(i, now, (1 << (i - 1)), i));
			}
			else if (arr[now][i]) {
				ret = min(ret, DFS(i, now, visit | (1 << (i - 1)), first) + arr[now][i]);
			}
		}
	}
	return ret;
}

int main() {
	cin >> N;
	memset(dp, 0x3f, sizeof(dp));
	MAXIMUM = dp[0][0][0];
	F(i, N)F(j, N)cin >> arr[i][j];
	for (int i = 1; i <= N; i++)MAX |= (1 << (i - 1));
	cout << DFS(0, 0, 0, 0);
}

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

문제

문제

출처

ICPC

반례가 궁금합니다.

melon940925 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말