글 읽기 - 틀리게 나온 input을 알고 싶습니다.

ldg1291 7년 전 0

비트마스킹을 이용하여 풀었습니다.

코드에 문제는 없어 보이는데 혹시 어떤 input에서 틀렸는지 알 수 있을까요??

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

int map[20][20];
int n;
int dp[20][1<<17];

int tsp (int start, int visited) {
    if(visited == (1<<n)-1) {
        if(map[start][1] != 0)
            return map[start][1];
    }
    
    int &res = dp[start][visited];
    
    if(res == -1) {
        res = 0xfffffff;
        for(int i=1; i<=n; i++) {
            if(!(visited & (1<<(i-1))) && map[start][i] != 0) {
                res = min(res, map[start][i] + tsp(i, visited | (1<<(i-1))));
            }
        }
    }
    
    return res;
}

int main(int argc, const char * argv[]) {
    
    scanf("%d", &n);
    
    memset(dp, -1, sizeof(dp)/sizeof(int));
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n ;j++) {
            scanf("%d", &map[i][j]);
        }
    }
    
    printf("%d\n", tsp(1,1));
    
    return 0;
}

zlzmsrhak 7년 전 0

반례만 달라고 하셔서 반례만 드립니다. 틀린 이유까지 알고싶으시면 다시 댓글 달아주세요.

16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

ldg1291 7년 전 0

memset부분이 틀린걸 발견해서 고쳐서 위 input에 대해서는 해결이 됐는데 역시나 틀렸다고 나오네요.. 혹시 어떤 부분에서 틀린건지 알 수 있을까요?? 감사합니다

zlzmsrhak 7년 전 0

memset만 고치면 맞을텐데요..?

ldg1291 7년 전 0

아 이 코드 다시 긁어서 memset 수정하니 되네요 뭔가 제가 전에 바꿔놓았던 듯 합니다 감사합니다!!

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

문제

문제

출처

ICPC

틀리게 나온 input을 알고 싶습니다.

ldg1291 7년 전 0

zlzmsrhak 7년 전 0

ldg1291 7년 전 0

zlzmsrhak 7년 전 0

ldg1291 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말