AcWing 最短哈密顿路径(状态压缩dp)

 1 /*
 2 哪些点走过了,和现在位于那个点上,是建立状态转移的关键
 3 */
 4 #include<iostream>
 5 #include<climits>
 6 #include<string>
 7 #include<cstring>
 8 using namespace std;
 9 const int N=20,M=1<<20;
10 int f[M][N];
11 int weight[N][N];
12 int main(void)
13 {
14     int n ;
15     cin>>n;
16     for(int i=0;i<n;i++)
17     {
18         for(int j=0;j<n;j++)
19         {
20             cin>>weight[i][j];
21         }
22     }
23     memset(f,0x3f,sizeof f);
24     f[1][0]=0;
25     for(int i=0;i<(1<<n);i++)//所有的状态
26     {
27         for(int j=0;j<n;j++)//遍历所有的点,先找出终点,然后用其他的点去松弛他
28         {
29             if(i>>j&1)//如果要到达的状态包含了j这个点
30             {
31                 for(int k=0;k<n;k++)//再找一个不同于j的点,进行权的松弛
32                 {
33                     if(((i-(1<<j))>>k)&1)//保证k!=j
34                     {
35                         f[i][j]=min(f[i][j],f[(i-(1<<j))][k]+weight[k][j]);
36                     }
37                 }
38             }
39         }
40     }
41     cout<<f[(1<<n)-1][n-1];
42     return 0;
43 }

 

上一篇:AcWing 587. 吃蛋糕


下一篇:poj3311 Hie with the Pie