题目大意：有一个人要去旅游，他想要逛遍所有的城市，但是同一个城市又不想逛超过2次。现在给出城市之间的来往路费，他可以选择任意一个点为起点。问逛遍所有城市的最低路费是多少
解题思路：这题和POJ - 3311 Hie with the Pie相似
这里的状态标记要用三进制数来表示，就可以表示每个城市去过的次数了
设dp[i][state]为现在在i城市，逛过的城市状态为state的最低路费
状态转移方程：
dp[i][S ＋ i城市标记] = min(dp[i][S + i城市标记], dp[j][S] + cost[j][i])
注意给边判重
又用了队列。。。
#include
#include
#include
#include
using namespace std; #define maxn 15 #define INF 0x3f3f3f3f #define maxs 60000 struct DP { int num, state; }start[maxn]; int n, m; int cost[maxn][maxn]; int dp[maxn][maxs]; int mod[maxn]; void init() { int x, y, z; memset(cost, 0x3f, sizeof(cost)); for(int i = 0; i < m; i++) { scanf(%d%d%d, &x, &y, &z); cost[x-1][y-1] = cost[y-1][x-1] = min(cost[x-1][y-1], z); } memset(dp, 0x3f, sizeof(dp)); for(int i = 0; i < n; i++) { dp[i][mod[i]] = 0; start[i].num = i; start[i].state = mod[i]; } } void solve() { queue
q; for(int i = 0; i < n; i++) q.push(start[i]); int ans = INF; while(!q.empty()) { DP t = q.front(); q.pop(); for(int i = 0; i < n; i++) { if(i == t.num || cost[i][t.num] == INF) continue; if(!i && t.state % 3 == 2) continue; if(i && ( (t.state % mod[i+1]) - (t.state % mod[i]) ) / mod[i] == 2) continue; if(dp[i][t.state + mod[i]] > dp[t.num][t.state] + cost[t.num][i]) { dp[i][t.state + mod[i]] = dp[t.num][t.state] + cost[t.num][i]; DP tt; tt.num = i; tt.state = t.state + mod[i]; q.push(tt); bool flag = false; int tmp = t.state + mod[i]; if(dp[i][tmp] < ans) { for(int j = 0; j < n; j++) if(tmp % 3 == 0) { flag = true; break; } else { tmp /= 3; } if(!flag) ans = dp[i][t.state + mod[i]]; } } } } if(ans == INF) ans = -1; printf(%d , ans); } void begin() { mod[0] = 1; for(int i = 1; i < 12; i++) mod[i] = mod[i - 1] * 3; } int main() { begin(); while(scanf(%d%d, &n, &m) != EOF) { init(); solve(); } return 0; }
?