HDU - 3001 Travelling 状压dp + 三进制 [kuangbin带你飞]专题二

        终于刷完搜索专题了。

      题意：给定n个城市，每个城市参观不能超过两次，两个城市之间有道路通过需要花费X，求通过能所有城市的最小花费。

     思路：每个城市有三个状态0,1,2，可用三进制存储所有城市的访问状态。DP[i][j]表示当前状态为i，j是道路的最后一个城市。

    如果j城市可以到达k城市，那么下一个状态就是next = i + bit[k]，转移方程DP[next][k] = min(DP[next][k], DP[i][j] + cost[j][k]),cost[j][k]表示城市j到k的花费。

AC代码： 374ms

#include<cstdio>#include<vector>#include<algorithm>#include<cstring>#include<utility>using namespace std;typedef pair<int, int> PI;const int inf = 0x3f3f3f3f;const int maxn = 60000;int num[maxn][15], bit[15], cost[15][15], dp[maxn][15];void init() {	bit[0] = 1;	for(int i = 1; i <= 10; ++i) 		bit[i] = bit[i - 1] * 3;	for(int i = 0; i < bit[10]; ++i) {		int x = i;		for(int j = 0; j < 10; ++j) {			num[i][j] = x % 3;			x /= 3;		}	}}int main() {	init();	int n, m;	while(scanf("%d%d", &n, &m) == 2) {		memset(cost, -1, sizeof(cost));		int x, y, c;		for(int i = 0; i < m; ++i) {			scanf("%d%d%d", &x, &y, &c);			if(cost[x-1][y-1] == -1) {				cost[x-1][y-1] = cost[y-1][x-1] = c;			}			else {				cost[x-1][y-1] = cost[y-1][x-1] = min(cost[x-1][y-1], c); //去重边 			}		}				memset(dp, inf, sizeof(dp));		//初始化边界		for(int i = 0; i < n; ++i) {			dp[ bit[i] ][i] = 0;		} 		int ans = inf;		for(int i = 0; i < bit[n]; ++i) {			int flag = 1;			for(int j = 0; j < n; ++j) {				if(num[i][j] == 0) flag = 0; //当前状态有从未经过的点				if(dp[i][j] == inf) continue;								for(int k = 0; k < n; ++k) {					if(k == j || num[i][k] >= 2 || cost[j][k] == -1) continue;					int walk = i + bit[k]; //转换到新的状态					dp[walk][k] = min(dp[walk][k], dp[i][j] + cost[j][k]); 				} 			}			if(flag) {				for(int j = 0; j < n; ++j) ans = min(ans, dp[i][j]);			}		}		if(ans == inf) ans = -1;		PRintf("%d/n", ans);	} 		return 0;}如有不当之处欢迎指出！