終于刷完搜索專題了。

      題意：給定n個城市，每個城市參觀不能超過兩次，兩個城市之間有道路通過需要花費X，求通過能所有城市的最小花費。

     思路：每個城市有三個狀態(tài)0,1,2，可用三進制存儲所有城市的訪問狀態(tài)。DP[i][j]表示當前狀態(tài)為i，j是道路的最后一個城市。

    如果j城市可以到達k城市，那么下一個狀態(tài)就是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; //當前狀態(tài)有從未經過的點				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]; //轉換到新的狀態(tài)					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;}如有不當之處歡迎指出！