글 읽기 - 외판원 문제 도와주십시오

beawall 2년 전 0

단순 dfs로 풀면 시간초과가 나서 dp를 도입해서 푼다고 풀었는데 문제 예시부터 답이 제대로 안나오고 미묘하게 자꾸 큰값이 나옵니다. 찬찬히 따라가봐도 코드 어디에 문제가 있는지 모르겠어요..

//어차피 모든 점을 돌기 때문에 시작점은 의미없음
#include <iostream>
#include <memory.h>
using namespace std;
int adjmat[16][16];
int dp[65600][16];
int n, allvisit;
const int INF = 1e8;
int pow()
{
    int mul = 1, i = n;
    while (i--)
        mul *= 2;
    return mul;
}
//visit은 각 점의 방문 여부를 표시할 비트마스크 변수
//시작점은 0으로 함
int func(int visit, int now)
{
    int minval = INF, tmp1, tmp2;
    if (dp[visit][now] != -1)
        return dp[visit][now];
    if (visit == allvisit)
    {
        if (!adjmat[now][0])
            return INF;
        else
            return adjmat[now][0];
    }
    for (int i = 1; i < n; i++)
    {
        if (!adjmat[now][i] || (visit >> i) & 1 == 1)
            continue;
        tmp1 = func(visit | 1 << i, i);
        if (minval > tmp1)
        {
            minval = tmp1;
            tmp2 = adjmat[now][i];
        }
    }
    dp[visit][now] = tmp2 + minval;
    return tmp2 + minval;
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    allvisit = pow() - 1;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> adjmat[i][j];
    cout << func(1, 0) << '\n';
    return 0;
}

kdh6429 2년 전 1

tmp2 는 if 문 조건을 타야만 활용이 가능할 것 같네요.

beawall 2년 전 0

말씀 듣자마자 바로 보이네요.. 대단하십니다

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

문제

문제

출처

ICPC

외판원 문제 도와주십시오

beawall 2년 전 0

kdh6429 2년 전 1

beawall 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말