最短Hamilton路径

题面描述

给定一张 $n$ 个点的带权无向图,点从 $0$ 到 $n-1$ 标号,求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。
Hamilton路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$ 。
接下来 $n$ 行每行 $n$个整数,其中第 $i$行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离(记为 $a_{i,j}$ )。
对于任意的 $x,y,z$ ,数据保证 $a_{x,x}=0$ ,$a_{x,y}=a_{y,x}$ 并且 $a_{x,y}+a_{y,z}>=a_{x,z}$ 。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

$1≤n≤20$
$0≤a_{i,j}≤10^7$
输入样例:
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例:
18

解题思路

状压dp

用dpi表示经过了 二进制i 中为1的点,当前点为j。(其中l为1<<20)
用类似floyd算法,可得出: $dp[i][j]=min(dp[i][j],dp[i-1<<j][k]+dis[j][k])$
但是在此之前必须满足两个条件:
1.i中经过j,即这个元素是存在的
2.i中经过k,即可以以k为中转点转到j

代码

#include<bits/stdc++.h>
using namespace std;
long long dp[1<<20][25];
int m[25][25];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>m[i][j]; 
        }
    }
    for(int i=0;i<1<<20;i++){
        for(int j=0;j<25;j++){
            dp[i][j]=2147483647;
        }
    }
    dp[1][0]=0;
    for(int i=1;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if(i>>j&1){//如果到过j点 
                for(int k=0;k<n;k++){//以k为中转点到k 
                    if(i>>k&1){//i-(1<<j)表示除去j点, 
                        dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+m[k][j]);
                    }
                }
            } 
        }
    }
    cout<<dp[(1<<n)-1][n-1];
    return 0;
} 

本文链接:https://kaispace.com.cn/index.php/archives/476/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者