题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3001
题目：
题意：n个城市，m条边，每条边都有一个权值，问你经过所有的城市且每条边通过次数不超过两次的最短距离。
思路：状压dp+三进制，dp[i][j]表示在状态i下以j为目标城市的最短距离，转移方程为nw = i + fi[k];dp[nw][k] = min(dp[nw][k], dp[i][j] + mp[j][k])。
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 16 typedef long long ll; 17 typedef pair<ll, ll> pll; 18 typedef pair<ll, int> pli; 19 typedef pair<int, ll> pil;; 20 typedef pair<int, int> pii; 21 typedef unsigned long long ull; 22 23 #define lson i<<1 24 #define rson i<<1|1 25 #define bug printf("********* "); 26 #define FIN freopen("D://code//in.txt", "r", stdin); 27 #define debug(x) cout<<"["<<x<<"]" <<endl; 28 #define IO ios::sync_with_stdio(false),cin.tie(0); 29 30 const double eps = 1e-8; 31 const int mod = 10007; 32 const int maxn = 60000 + 7; 33 const double pi = acos(-1); 34 const int inf = 0x3f3f3f3f; 35 const ll INF = 0x3f3f3f3f3f3f3f; 36 37 int n, m, u, v, w; 38 int mp[15][15], dp[maxn][15], fi[15], state[maxn][15]; 39 40 void init() { 41 fi[1] = 1; 42 for(int i = 2; i <= 10; i++) { 43 fi[i] = fi[i-1] * 3; 44 } 45 for(int i = 0; i < 60007; i++) { 46 int t = i; 47 for(int j = 1; j <= 10; j++) { 48 state[i][j] = t % 3; 49 t /= 3; 50 if(t == 0) break; 51 } 52 } 53 } 54 55 int main() { 56 //FIN; 57 init(); 58 while(~scanf("%d%d", &n, &m)) { 59 memset(mp, inf, sizeof(mp)); 60 memset(dp, inf, sizeof(dp)); 61 for(int i = 1; i <= n; i++) { 62 mp[i][i] = 0, dp[fi[i]][i] = 0; 63 } 64 for(int i = 1; i <= m; i++) { 65 scanf("%d%d%d", &u, &v, &w); 66 mp[u][v] = mp[v][u] = min(mp[u][v], w); 67 } 68 int ans = inf; 69 for(int i = 0; i < 3 * fi[n]; i++) { 70 int flag = 1; 71 for(int j = 1; j <= n; j++) { 72 if(state[i][j] == 0) flag = 0; 73 if(dp[i][j] >= inf) continue; 74 for(int k = 1; k <= n; k++) { 75 if(j == k) continue; 76 if(mp[j][k] >= inf || state[i][k] >= 2) continue; 77 int nw = i + fi[k]; 78 dp[nw][k] = min(dp[nw][k], dp[i][j] + mp[j][k]); 79 } 80 } 81 if(flag) { 82 for(int j = 1; j <= n; j++) { 83 ans = min(ans, dp[i][j]); 84 } 85 } 86 } 87 if(ans >= inf) printf("-1 "); 88 else printf("%d ", ans); 89 } 90 return 0; 91 }