글 읽기 - 혹시 테스트 케이스 주실 수 있을까요

ybs1164 3년 전 0

플로이드 와샬로 최단거리 구한 뒤에 외판원 순외 돌리면 될 줄 알았는데 안되는군요..?

도와주세요 ㅠ

#include <stdio.h>
#include <string.h>
#include <algorithm>
int n,k;
int a[11][11];
int d[11][1024];

int f(int x,int v){
    if (v==(1<<n)-1)
        return 0;

    int &ret=d[x][v];
    if (ret!=-1) return ret;

    ret=2147483647;

    for (int i=0;i<n;i++){
        if (v&(1<<i)) continue;
        if (!a[x][i]) continue;
        ret=std::min(ret,a[x][i]+f(i,v+(1<<i)));
    }

    return ret;
}

int main(){
    scanf("%d %d",&n,&k);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    memset(d,-1, sizeof(d));

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            for (int k=0;k<n;k++){
                if (a[j][k]>a[j][i]+a[i][k]){
                    a[j][k]=a[j][i]+a[i][k];
                }
            }
        }
    }

    printf("%d",f(k,1<<k));

    return 0;
}

jinsoolve 2년 전 2

19번째 줄을 지우기만 하면 됩니다.

의도하신 코드는 x == i 일 때 continue이신 것 같은데(추측입니다...) 그 부분은 이미 18번째 줄에서 continue하고 있습니다.

그런데 a[x][i] == 0 일 때 continue를 또 시켜주면서 아래와 같은 반례가 생기게 됩니다.

2 0
0 0
0 0

correct: 0
wrong: 2147483647

ybs1164 2년 전 0

이이런...

압도적 감사를 드립니다

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

문제

문제

출처

ICPC

혹시 테스트 케이스 주실 수 있을까요

ybs1164 3년 전 0

jinsoolve 2년 전 2

ybs1164 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말