题目链接:
https://vjudge.net/contest/159644#problem/D
题意:
n个点，给出m条边，每条边有一个边权，每个顶点可以走两次
问走遍所有点的最小花费
题解:
http://www.cnblogs.com/martinue/p/5490432.html
对于状态S，第i位为1表示已经走过
dp[S][v]:=在S这个状态，走到v所用的花费
转移： dp[i+three[k]][k] = min(dp[i+three[k]][k],dp[i][j]+g[j][k]);
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 60000; 17 18 int three[11]; 19 int dp[maxn][11],digit[maxn][11]; 20 int g[11][11]; 21 int n,m; 22 23 void init(){ 24 three[0] = 1; 25 for(int i=1; i<11; i++) 26 three[i] = three[i-1]*3; 27 28 for(int i=0; i<three[10]; i++){ 29 int tmp = i; 30 for(int j=0; j<10; j++){ 31 digit[i][j] = tmp%3; 32 tmp /= 3; 33 } 34 } 35 } 36 37 int main(){ 38 init(); 39 while(cin>>n>>m){ 40 for(int i=0; i<n; i++) 41 for(int j=0; j<n; j++) 42 g[i][j] = INF; 43 for(int i=0; i<three[n]; i++) 44 for(int j=0; j<n; j++) 45 dp[i][j] = INF; 46 while(m --){ 47 int u,v,w; 48 cin >> u >> v >> w; 49 g[u-1][v-1] = g[v-1][u-1] = min(w,g[u-1][v-1]); 50 } 51 for(int i=0; i<n; i++) 52 dp[three[i]][i] = 0; 53 int ans = INF; 54 for(int i=0; i<three[n]; i++){ 55 bool flag = 1; 56 for(int j=0; j<n; j++){ 57 if(digit[i][j] == 0) flag=0; 58 if(dp[i][j] != INF){ 59 for(int k=0; k<n; k++) 60 if(g[j][k]!=INF && digit[i][k]!=2) 61 dp[i+three[k]][k] = min(dp[i+three[k]][k],dp[i][j]+g[j][k]); 62 } 63 } 64 if(flag){ 65 for(int j=0; j<n; j++) 66 ans = min(dp[i][j],ans); 67 } 68 } 69 if(ans == INF) puts("-1"); 70 else cout << ans << endl; 71 } 72 73 return 0; 74 } 75 // http://www.cnblogs.com/martinue/p/5490432.html