poj 3311(状态压缩dp)

最新推荐文章于 2019-08-18 08:06:51 发布

weiwei2012start

最新推荐文章于 2019-08-18 08:06:51 发布

阅读量769

点赞数

本文链接：https://blog.csdn.net/sxwup/article/details/10274837

版权

/*
  dp[s][i] =min{dp[s][i],dp[s'][j]+map[j][i]} map[j][i]为j到i的最短距离
*/ 


#include <stdio.h>
#include <string.h>

#define inf 100000000   
 
int map[12][12];   
int dp[1<<11][12];

int min(int x,int y)
{
  if(x<y) return x;
  return y;    
}


int main()
{
    int n;
    
  while(scanf("%d",&n)!=EOF)
  {
      if(n==0)  break;
      
      for(int i=0;i<=n;i++)
         for(int j=0;j<=n;j++)
            scanf("%d",&map[i][j]);
            
      for(int k=0;k<=n;k++)
         for(int i=0;i<=n;i++)
           for(int j=0;j<=n;j++)
             if(map[i][j]>map[i][k]+map[k][j])
               map[i][j]=map[i][k]+map[k][j];
      
     // memset(dp,-1,sizeof(dp));
      
      for(int s=0;s<(1<<n);s++)  //所有的状态 
      {
          for(int i=1;i<=n;i++)    
          {
             if(s&(1<<(i-1)))    // 状态s中经过i城市 
             {
                 if(s==(1<<(i-1)))   //  状态s中只经过i城市 
                   dp[s][i] = map[0][i];
                 else                // 经过多个城市 
                 {
                    dp[s][i]=inf;
                    for(int j=1;j<=n;j++)
                    {
                       if(s&(1<<(j-1)) && i!=j) ///枚举不是城市I的其他城市  
                        dp[s][i] = min(dp[s][i],dp[s^(1<<(i-1))][j]+map[j][i]);
                        //在没经过城市i的状态中，寻找合适的中间点J使得距离更短
                     }    
                 }            
             }
         }
      }
      
      
      int ans=dp[(1<<n)-1][1]+map[1][0];
      
      
      for(int i=2;i<=n;i++)
      {
         if(dp[(1<<n)-1][i]+map[i][0]<ans)
         {
           ans = dp[(1<<n)-1][i]+map[i][0];                                
         }
      }
      
      printf("%d\n",ans);
  }
    
  return 0;
}