【POJ3311】Hie with the Pie（状压DP，最短路）

时间：2023-03-08 20:27:22

题意：

【POJ3311】Hie with the Pie（状压DP，最短路）

思路：状压DP入门题

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #define oo 1000000000

 #define N (1<<12)-1

 using namespace std;

 int dp[N][];

 int f[][];

 int n;

 int main()

 {

     //freopen("poj3311.in","r",stdin);

     //freopen("poj3311.out","w",stdout);

     while(scanf("%d",&n)==&&n)

     {

         n++;

         for(int i=;i<=n;i++)

          for(int j=;j<=n;j++) scanf("%d",&f[i][j]);

         int MAX=(<<n)-;

         for(int i=;i<=MAX;i++)

          for(int j=;j<=n;j++) dp[i][j]=oo;

         for(int i=;i<=n;i++)

          for(int j=;j<=n;j++)

           for(int k=;k<=n;k++)

            if((i!=j)&&(i!=k)&&(j!=k)) f[j][k]=min(f[j][k],f[j][i]+f[i][k]);

         dp[][]=;

         for(int sta=;sta<=MAX;sta++)

          for(int i=;i<=n;i++)

           for(int j=;j<=n;j++)

            if(!(sta&(<<(j-)))) dp[sta|(<<(j-))][j]=min(dp[sta|(<<(j-))][j],dp[sta][i]+f[i][j]);

         int ans=oo;

         for(int i=;i<=n;i++) ans=min(ans,dp[MAX][i]+f[i][]);

         printf("%d\n",ans);

     }

     return ;

 }

相关文章