POJ 3311 Hie with the Pie 先用floyd预处理,再状态压缩

时间:2023-02-05 03:59:34

下面是别人的解题报告链接:

http://blog.csdn.net/accry/article/details/6607703

下面是我的代码,我觉得链接中的代码有一点小问题,也许是我想错了吧。

 #include <cstdio>
#define min(a,b) (a) < (b) ? (a) : (b);
#define INF 100000000
int dist[][];
int dp[][];
void init(int n)
{
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
scanf("%d",&dist[i][j]);
for(int k =; k <=n; ++k)
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main()
{
// freopen("in.cpp","r",stdin);
int n;
while(scanf("%d",&n), n)
{
init(n);
int sn = <<(n+);//状态数
for(int i=; i<sn; ++i)
for(int j=; j<=n; ++j)
dp[i][j] = INF;
for(int i=; i<=n; ++i)
dp[(<<i)][i] = dist[][i];
for(int k=; k<sn; ++k)
{
for(int i=; i<=n; ++i)
{
if(! (k & (<<i) )) continue;
for(int j=; j<=n; ++j)
{
if( j != i && k & ( << j) )
dp[k][i] = min(dp[k][i] , dp[k^(<<i)][j]+dist[j][i] );
}
}
}
printf("%d\n",dp[sn-][]);
}
return ;
}