HDU - 3538 A Sample Hamilton path

이것은 상압 dp???아니면 상압 dp의 문제집에 나타났거나...나...
dp[i][j]는 i 상태에서 마지막 점은 j의 최소값에 도달한다.
후 정상상압 dp의 전이 과정에 따라다음은 ac 코드입니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int dp[1<<21][22];
int dis[21][21];
int p[22];
int main()
{
     
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
     
        memset(p, 0, sizeof(p));
        int mx = (1 << n) - 1;
        for (int i = 0; i <= mx; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j] = inf;
        for (int i = 0; i < n; i++)
        {
     
            for (int j = 0; j < n; j++)
            {
     
                scanf("%d", &dis[i][j]);
                if (dis[i][j] == -1) dis[i][j] = inf;
            }
        }
        for (int i = 1; i <= m; i++)
        {
     
            int x, y;
            scanf("%d%d", &x, &y);
            p[y] |= (1<<x);
        }
        dp[1][0] = 0;
        for (int i = 1; i <= mx; i++)
        {
     
            for (int j = 0; j < n; j++)
            {
     
                if(dp[i][j] == inf) continue;
                for (int k = 1; k < n; k++)
                {
     
                    if (!(i&(1<<j))) continue;
                    if (i&(1<<k)) continue;
                    if ((p[k] | i) != i) continue;
                    dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + dis[j][k]);
                }
            }
        }
        int ans = inf;
        for (int i = 0; i < n; i++)
        {
     
            ans = min(ans, dp[mx][i]);
        }
        if (ans >= inf) puts("-1");
        else printf("%d
", ans);
    }
    return 0;
}