题目大意

给定一个n个点的完全有向图,求从1号点出发,经过所有的点后回到1号点的最短路径长。(n\leq 20)

算法讲解

记忆化搜索是个好东西。
首先考虑暴力dfs。dfs(x)表示现在在x号点上,每次枚举一个未经过的点进行搜索,复杂度为O(n!),显然在n=20的数据范围内会时间超限。

然而很多情况下,搜索会面临许多一样的状态,例如走过1~5号点,并且现在在5号点上的状态,就有3!种,但是从5号点出发,并走到结束状态的最优解是永远相同的,所以可以考虑把这个状态的最优解记录下来。
mem[x][t]表示了一个状态的最优解,x表示目前所处的结点,t表示已经走过的结点状态,当且仅当mem[x][t]没有值的时候才会通过搜索更新,可以保证每一个状态只被更新一遍,所以复杂度降到了O(n\time 2^n)

#include<cstdio>
#include<algorithm>
#define INF 1000000000;
using namespace std;
int n,a[21][21],mem[21][1<<21];
int dfs(int x,int t){
    if(t==(1<<n)-1)
        return mem[x][t]=a[x][1];
    int ret=INF;
    for(int i=1<<(n-1),j=n;i;i>>=1,--j){
        if((t|i)!=t){
            if(mem[j][t|i]){
                ret=min(ret,mem[j][t|i]+a[x][j]);
            }else{
                ret=min(ret,dfs(j,t|i)+a[x][j]);
            }
        }
    }
    return mem[x][t]=ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        scanf("%d",&a[i][j]);
    printf("%d\n",dfs(1,1));
}

"Alone is what I have. Alone protects me." -Sherlock Holmes