题目链接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%20%E6%9C%80%E7%9F%ADHamilton%E8%B7%AF%E5%BE%84

 

第一次接触状态压缩dp

 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000 + 10;
const int inf = 0x7fffffff;
int n;
int d[(1 << 20)+10][20+10];
int w[22][22];
int hamliton(){
    memset(d, 0x3f, sizeof d);   //给d初始化为无穷
    d[1][0] = 0;
    for (int i = 1; i < (1 << n);i++)
    for (int j = 0; j < n; j++) if ((i>>j)&1) //取出i里面的第j位
    for (int k = 0; k < n; k++) if (((i ^ (1 << j)) >> k) & 1) //在去掉j的情况下，取出i里面的第k位
        d[i][j] = min(d[i][j], d[i ^ (1 << j)][k] + w[k][j]);

    return d[(1 << n) - 1][n - 1];
}
int main()
{
    cin >> n;
    for (int i = 0; i < n;i++)
    for (int j = 0; j < n; j++)
        cin >> w[i][j];
    cout << hamliton() << endl;
    
    return 0;
}

View Code