POJ 3311 floyd+压状DP

poj3311
因为这道题 点N 不超过10 可以 把状态转化 为 二进制数，0表示没经过这个点，1表示经过这个点。
dp[i][j] 表示的是 在 i 状态 下 到达j 的最短路径

#include<cstdio>
#include<cstring>
using namespace std;
int mapp[11][11];
int dp[1<<13][13];
int n;
int main()
{
   while(~scanf("%d",&n)&&n)
   {
      memset(mapp,0,sizeof(mapp));
      memset(dp,-1,sizeof(dp));
       for(int i=0;i<=n;i++)
       {
           for(int j=0;j<=n;j++)
           {
               scanf("%d",&mapp[i][j]);
           }
       }
       for(int k=0;k<=n;k++)
       {
           for(int i=0;i<=n;i++)
           {
               for(int j=0;j<=n;j++)
               {
                         if(mapp[i][j]>mapp[i][k]+mapp[k][j])
                         {
                              mapp[i][j]=mapp[i][k]+mapp[k][j];
                         }

               }
           }
       }
       dp[1][0]=0;
       for(int i=1;i<(1<<(n+1));i++)
       {
           i=i|1;
           for(int j=0;j<=n;j++)
           {   // 可以 这个状态可以 到达 j
               if(dp[i][j]!=-1)
               {
                   for(int k=0;k<=n;k++)
                   {
                       if(j!=k&&(dp[i|(1<<k)][k]==-1||(dp[i|(1<<k)][k]>dp[i][j]+mapp[j][k])))
                       {
                           // 这个状态 到达 k  为 状态 i 到达 j 的 最短路到达
                          dp[i|(1<<k)][k]=dp[i][j]+mapp[j][k];
                       }
                   }
               }
           }
       }
       printf("%d\n",dp[(1<<(n+1))-1][0]);
   }
    return 0;
}

hdu5418
题目跟上一题 略有不同，我是在之前的代码上改的。
所以下标都减一。

#include<cstdio>
#include<cstring>
using namespace std;
int mapp[18][18];
int dp[1<<18][18];
int n,m;
int a,b,v;
int main()
{  int t;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d",&n,&m);
      memset(mapp,-1,sizeof(mapp));
      memset(dp,-1,sizeof(dp));
      for(int i=0;i<m;i++)
      {
          scanf("%d%d%d",&a,&b,&v);
          a--;
          b--;
          int te=mapp[a][b];
          if(te==-1||te>v)
          {
              mapp[a][b]=v;
              mapp[b][a]=v;
          }
      }
       for(int k=0;k<n;k++)
       {
           for(int i=0;i<n;i++)
           {
               for(int j=0;j<n;j++)
               {
                   if(mapp[i][k]!=-1&&mapp[k][j]!=-1)
                   {
                       if(mapp[i][j]==-1||(mapp[i][j]>mapp[i][k]+mapp[k][j]))
                       {
                             mapp[i][j]=mapp[i][k]+mapp[k][j];
                       }
                   }
               }
           }
       }
       dp[1][0]=0;
       for(int i=1;i<(1<<(n));i++)
       {
           i=i|1;
           for(int j=0;j<n;j++)
           {   // 可以 这个状态可以 到达 j
               if(dp[i][j]!=-1)
               {
                   for(int k=0;k<n;k++)
                   {
                       if(j!=k&&(dp[i|(1<<k)][k]==-1||(dp[i|(1<<k)][k]>dp[i][j]+mapp[j][k])))
                       {
                           // 这个状态 到达 k  为 状态 i 到达 j 的 最短路到达
                          dp[i|(1<<k)][k]=dp[i][j]+mapp[j][k];
                       }
                   }
               }
           }
       }
       printf("%d\n",dp[(1<<(n))-1][0]);
   }
    return 0;
}