TSP 旅行商问题(状态压缩dp)

题意：有n个城市，有p条单向路径，连通n个城市，旅行商从0城市开始旅行，那么旅行完所有城市再次回到城市0至少需要旅行多长的路程。

思路：n较小的情况下可以使用状态压缩dp，设集合S代表还未经过的城市的集合，那么dp[S][v]:当前旅行商还有集合S中的城市没有旅行，并且在城市v时走过的所有路径长度

参考代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<algorithm>

#include<string>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<functional>

using namespace std;

const int N_MAX=;

int n,p;//p为单向路径的数量

int d[N_MAX][N_MAX];

int dp[<<N_MAX][N_MAX];//dp[S][v]:集合S:还未去过的城市集合，v当前所在的城市，dp[0][0]表示所有城市都去过，且当前在0城市，所走过的路程

int main() {

    scanf("%d%d",&n,&p);

    for (int i = ; i < n; i++)

        fill(d[i], d[i] + n, INT_MAX / );

    for (int i = ; i < p; i++) {

        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        d[a][b] = c;

    }

        for (int S = ; S <  << n;S++) {

            fill(dp[S], dp[S] + n,INT_MAX/);

        }

        dp[( << n) - ][] = ;

        for (int S = ( << n) - ; S >= ; S--) {

            for (int v = ; v < n;v++) {//若当前在v城市

                for (int u = ; u < n; u++) {

                    if (S >> u & ) {//若u还没去过

                        dp[S&~( << u)][u] = min(dp[S&~( << u)][u],dp[S][v]+d[v][u]);

                    }

                }

            }

        }

        printf("%d\n",dp[][]);

return ;

}