0103 最短Hamilton路径

痛定思痛。 2022-01-22 03:13 210阅读 0赞

题目链接： [contest-hunter.org:83/contest/0x00「基本算法」例题/0103][contest-hunter.org_83_contest_0x00_0103] 最短Hamilton路径

本题，很容易想到一种方法。就是将所有的排列全部列举出来，然后计算。但是很明显这种方法会时间超限。所以考虑状态压缩。将所有的方法用二进制比表示出来。  
一个整数用二进制比表示出来。为1的位置表示经过，为0的表示没经过。同时，还需要考虑当前是在哪一个位置上。所以我们可以用dp\[i\]\[j\]表示经过的状态为i，并且当前在j点时候的最短路径。  
再考虑这个状态能由哪些状态转移过来得到。很明显，因为当前点是j，所以上一个状态的j的位置一定为0.而且上一个状态的最终位置是可以为上一个状态中的任意一个点的。所以需要遍历考虑。

dp\[i\]\[j\] = min(dp\[i ^ (1 << j\]\[k\] + Graph\[k\]\[j\],dp\[i\]\[j\])

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define INF 0x3f
    
    int n,Graph[25][25];
    int dp[1 << 20][25];
    
    int main()
    {
        scanf("%d",&n);
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                scanf("%d",&Graph[i][j]);
        memset(dp,0x3f,sizeof(dp));
        dp[1][0] = 0;
        for(int i = 1; i < (1 << n); i ++)
        {
            for(int j = 0; j < n; j ++)
                if(i & (1 << j) != 0)
                {
                    for(int k = 0; k < n; k ++)
                        if((i ^ (1 << j)) & (1 << k))
                        {
                            dp[i][j] = min(dp[i ^ 1 << j][k] + Graph[k][j],dp[i][j]);
                        }
                }
        }
        printf("%d\n",dp[(1 << n) - 1][n - 1]);
    }

[contest-hunter.org_83_contest_0x00_0103]: http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0103