题目意思：给出n个城市，每个节点允许至多访问2次，问访问所有城市1遍，最小的花费是多少？
这个和tsp的区别就是每个城市可以访问2遍，思想一样，都是用一个位来表示当前状态，这个用三进制来表示，10个城市最大状态值为
3^10 -1=59048。之前tsp是用dfs来递归搜索的，这次正向扩展状态，思想都是一样的
dp[i][st]表示到达城市i状态为st的值，我们的目前就是求最小的dp[i][st]，并且st满足没有未访问的城市。
转移方程为：dp[j][st] = min{dp[j][st], dp[i][prest]+road[i][j]}，这里需要满足限制条件，就是prest中第i位不能为2，因为至多访问2次，
并且i和j之间有路可走。
View Code
#include <iostream> #include <stdio.h> using namespace std; const int MAXN=11; const int BASE = 3; const int MAXSTATE=60000; const int MAXDIS = 0xfffffff; int dp[MAXN][MAXSTATE];//到达城市j，状态为st的花费 int digit[MAXSTATE][MAXN];//状态st时，第i个城市的访问次数0,1,2 int basepow[MAXN]={1,3,9,27,81,243,729,2187,6561,19683,59049}; int road[MAXN][MAXN]; int n = 0, m = 0; void init() { int i = 0, j = 0, k = 0; for(i = 0; i < MAXSTATE; ++i) for(j = 0; j < MAXN; ++j) digit[i][j] = 0; for(i = 0; i < MAXSTATE; ++i) { int t = i; for(j = 0; j < MAXN; ++j) { digit[i][j] = t%BASE; t /= BASE; if(0 == t) break; } } } inline getmin(int a, int b) { return a < b ? a : b; } int main() { init(); int i, j, a, b, w; while(EOF != scanf("%d%d", &n, &m)) { for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) road[i][j] = MAXDIS; for(i = 0; i < m; ++i) { scanf("%d%d%d", &a, &b, &w); if(w < road[a-1][b-1]) { road[a-1][b-1]=w; road[b-1][a-1]=w; } } int k = 0; int st = 0; int nst = 0; int ans = MAXDIS; bool flag = true; for(i = 0; i < n; ++i) for(st = 0; st < basepow[n]; ++st) dp[i][st] = MAXDIS; for(i = 0; i < n; ++i) dp[i][basepow[i]] = 0; for(st = 0; st < basepow[n]; ++st) //every state { flag = true; for(i = 0; i < n; ++i) //当前城市i，扩展到城市j { if(0 == digit[st][i])//还有城市未访问 flag = false; if(dp[i][st] == MAXDIS)//该状态下城市i还未访问 continue; for(j = 0; j < n; ++j) { if(i == j) continue; if(road[i][j] == MAXDIS || 2 == digit[st][j]) continue; nst = st + basepow[j]; dp[j][nst] = getmin(dp[j][nst], dp[i][st]+road[i][j]); } } if(flag) { for(i = 0; i < n; ++i) ans = getmin(ans, dp[i][st]); } } if(MAXDIS == ans) puts("-1"); else printf("%d\n", ans); } return 0; }