题解 P1171 【售货员的难题】

Chupeiz · 2018-10-16 20:51:01 · 题解

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[25][25],dp[1100010][25],i,j,k;
//a用于储存初始矩阵距离,dp第一维表示一种状态（每种状态用一个数字表示）,里面存的是这种状态下的最短路径 
//（二进制数，1代表访问过，0代表没有访问过，所以要用位运算）
//第二维表示这种状态到达的编号 
//注意dp第一维的大小，即状态的总数为什么是1100010？
//n最大的情况下可以到20，那么我们至少需要在二进制形式下的111…111（一共20位表示其状态
//转换成10进制后的数字就差不多是这个
int ans=9999999;//ans初始化，下面会找最短路

inline int read() {//快速读入
    int sum=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum;
}

int main() {
    int n;
    n=read();
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            a[i][j]=read();
    memset(dp,67,sizeof(dp));//初始化dp，下面会找最短路
    dp[1][1]=0;//初始化，起点（1号点）到它自己的路径显然为0，为后文的动规做铺垫
    for (i=0; i<=(1<<n)-1; i++)//1左移n位，在二进制下除最高位以外都是0，再减1后每一位都是1
        for (j=1; j<=n; j++)
            if(((1<<j-1)&i)==0)//重点！(1<<j)-1是一种新状态，这里看它与i状态是不是一样的，如果已经出现过了，就不用再继续接下来的操作了
                for (k=1; k<=n; k++)
                    if(((1<<k-1)&i))  //重要！必须是曾出现过（或者说曾更新过的）的点才能作为中转点，不然是不会更新的
                        //故其相与值为1
                        dp[i|(1<<j-1)][j]=min(dp[i|(1<<j-1)][j],dp[i][k]+a[k][j]);
    for (i=2; i<=n; i++) {
        if((dp[(1<<n)-1][i]+a[i][1])<ans)//zwy太清晰了！ 
            ans=dp[(1<<n)-1][i]+a[i][1];//找最短的一条路，1<<n-1这种状态表示所有点都遍历了
    }
    printf("%d",ans);
    return 0;
}