poj3311 상태 압축

2817이랑 비슷해요.
비록 작지만 매우 전형적이기 때문에 작문을 해서 기록한다.
전체 배열 후의 최우수치를 구하다.
dp[i][j]는 상태가 j일 때, i번째가 마지막으로 추가되었을 때의 최우수값을 나타낸다

#include <iostream>
using namespace std;
#define oo 10000000
int p[11]={1,2,4,8,16,32,64,128,256,512,1024};
int g[11][11],dp[11][1026],n,ans;
int main() {
    while (scanf("%d",&n)) {
          if (n==0) break;
          for (int i=0;i<=n;i++)
              for (int j=0;j<=n;j++)
                  if (i==j) g[i][j] = 0;
                  else g[i][j] = oo;
          for (int i=0;i<=n;i++)
              for (int j=0;j<=n;j++)
                  scanf("%d",&g[i][j]);
          for (int k=0;k<=n;k++)
              for (int i=0;i<=n;i++)
                  for (int j=0;j<=n;j++)
                      if (i==j) continue;
                      else if (g[i][j]>g[i][k]+g[k][j])
                           g[i][j] = g[i][k] + g[k][j];
                  else dp[i][j] = oo;
          for (int j=0;j<p[n];j++)
              for (int i=1;i<=n;i++)
                  if (j==p[i-1]) dp[i][j] = g[0][i];
                  else 
                       if (j&p[i-1]) {
                                     dp[i][j] = oo;
                                     for (int k=1;k<=n;k++)
                                         if ((k!=i) && (j&p[k-1]))
                                            dp[i][j] = min(dp[i][j],dp[k][j^p[i-1]]+g[k][i]);
                       }
          ans = oo;
          for (int i=1;i<=n;i++)
              ans = min(ans, dp[i][p[n]-1]+g[i][0]);
          printf("%d
",ans);
    }
    return 0;
}