状态压缩dp的第一题！
题意：Mr ACMer想要进行一次旅行，他决定访问n座城市。Mr ACMer 可以从任意城市出发，必须访问所有的城市至少一次，并且任何一个城市访问的次数不能超过2次。n座城市间有m条道路，每条道路都有一个费用。求Mr ACMer 完成旅行需要花费的最小费用。如果不能完成旅行，则输出-1。
由于城市可以最多被访问两次，所以我们用3进制数来状态压缩，每一位可以存在0，1，2这三个数。因此，如果表示状态的数在这n位上每一位都大于等于1，则就是符合题意的解，我们要从这些解中遴选出
最小花费。所以，这道题看起来是一个多起点多终点的dp，然而，我们可以把他的起点城市看成是他拜访的第1个城市，最开始这位旅行家是不在任何城市的，他抵达第1个城市的费用是0。
这样就是一个固定起点，多终点的dp了；
那么我们定义dp[i][j]---->表示到达状态(i,j)时的最小费用，其中i是我用来表示当前城市造访情况的编码数，而j表示的是我们最后造访的一个城市。
这里采用刷表法来进行状态的更新，所谓“刷表法”是指的用当前状态来更新当前状态可能影响得到的后续状态，即现在的状态值已知；
而“填表法”指的是用已经算出的所有子状态来计算现在的状态，即现在状态未知，要靠已知来计算。
刷新方程：dp[i+3v][v] = min(dp[i+3v][v],dp[i][j]+cost[v][j]);
AC时间：2270ms，有点慢。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define F 0x3f
#define INF 0x3f3f3f3f
#define maxn 60000
using namespace std;
int dp[maxn][];
int cost[][];
int carrys[];
int main()
{
int n,m;
carrys[] = ;
for(int i = ;i <= ;++i) carrys[i] = * carrys[i - ];
while(scanf("%d%d",&n,&m) == ){
memset(dp,F,sizeof(dp));
memset(cost,F,sizeof(cost));
int start,over,spend;
for(int i = ;i < m;++i){
scanf("%d%d%d",&start,&over,&spend);
--start,--over;
cost[start][over] = cost[over][start] = min(cost[start][over],spend);
}
for(int i = ;i < ;++i) dp[carrys[i]][i] = ;
int answer = INF;
for(int i = ;i <= carrys[] - ;++i){
bool is_qualified = true;
for(int j = ;j < n;++j){
if((i / carrys[j]) % == ) is_qualified = false;
}
for(int j = ;j < n;++j){
for(int k = ;k < n;++k){
if(k != j && (i / carrys[k]) % < ){
int u = i + carrys[k],v = k;
dp[u][v] = min(dp[u][v],dp[i][j] + cost[v][j]);
}
}
}
if(is_qualified){
for(int j = ;j < n;++j) answer = min(answer,dp[i][j]);
}
}
printf("%d\n",answer >= INF ? - : answer);
}
return ;
}