[HDOJ 5418] Victor and World(상압 dp)

[HDOJ 5418] Victor and World(상압 dp)
여행사 문제는 두려워하지 마세요. 16점밖에 없어요. 그래서 상압으로 하면 돼요. 플로이드는 각 점의 최소 거리를 초기화하고 상태 dp를 매거해요. 이 상태에 포함된 점 dp의 최소 거리.
마지막으로 dp 각 점이 전체 1 상태에서 가장 짧은 거리는 한 바퀴 돌고 돌아온 후의 가장 짧은 거리이다
코드는 다음과 같습니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
#define ll long long
#define INF 0x3f3f3f3f

int mp[16][16];
int dp[16][1<<16];

int main()
{
   // freopen("../../../in.in","r",stdin);
    int t,n,m,u,v,w,i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);

        memset(mp,INF,sizeof(mp));
        while(m--)
        {
            scanf("%d %d %d",&u,&v,&w);
            if(mp[u-1][v-1] > w) mp[u-1][v-1] = mp[v-1][u-1] = w;
        }

        for(k = 0; k < n; ++k)//floyd      
            for(i = 0; i < n; ++i)
                for(j = 0; j < n; ++j)
                    mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);

        memset(dp,INF,sizeof(dp));
        dp[0][1] = 0;//   0000000001  

        for(i = 1; i < (1<<n); ++i)//    
            for(j = 0; j < n; ++j)//    
                if((1<<j)&i)
                for(k = 0; k < n; ++k)//    
                    if((1<<k)&i) dp[j][i] = min(dp[j][i],dp[k][i^(1<<j)]+mp[j][k]);

        for(i = 1; i < n; ++i)//     
        {
            dp[0][(1<<n)-1] = min(dp[0][(1<<n)-1],dp[i][(1<<n)-1]+mp[i][0]);
        }
        printf("%d
",dp[0][(1<<n)-1]);
    }
    return 0;
}