poj 3311 Hie with the Pie (TSP)

dp[state][j] 表示在state的状态下 当前位置在j的最小路程

状态转移：dp[i][j]=min(dp[i][j],dp[i^(1<

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f using namespace std; int map[12][12]; int dis[12][12]; int dp[1<<12][12]; int main() { int n; while(scanf("%d",&n)!=EOF && n) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&map[i][j]); for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { dis[i][j]=map[i][j]; dis[i][i]=0; } for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dis[i][j]=dis[i][j]>dis[i][k]+dis[k][j] dis[i][k]+dis[k][j]:dis[i][j]; memset(dp,0,sizeof dp); for(int i=1;i<(1<<(n+1));i++) { i|=1; for(int j=1;j<=n;j++) { if((1<