哭瞎啊，每个城市可以经过至多两次，但没有要求必须经过两次，想用 两个状压来乱搞搞，结果自认为会T，结果 WA了，搞了一下午，没想到用三进制啊，智商捉急，参考了

http://blog.csdn.net/lenleaves/article/details/7980955 这个博客

每个城市可以经过1或2次，所以三进制可以代表所有状态了，接下来处理方式类似于二进制的，只是没有了位运算一些判断跟预处理有点繁琐

方程dp[s][i] = min(dp[s][i] , dp[s - (s除去j剩下状态)][k] + dis[k][j]),

由于没有固定的出发点，所以也就没有固定的终点，所以要以任何城市为终点的可能都要枚举到

dp[i][j]代表i状态下以 j为终点的最小花费

转移方程就是 ： i 状态以j为终点的递推为(i状态中不经过j位置的状态下以k为终点 + k到j所需距离)

#define MAXN 0x3f3f3f3f

int n,m;

int dp[100000 + 55][10 + 5];

int mp[10 + 5][10 + 5];

int s[59050][10 + 5];

void clear() {
	
	for(int i=0;i<59050;i++) {
		int tmp = i;
		for(int j=1;j<=10;j++) {
			s[i][j] = tmp%3;
			tmp /= 3;
			if(!tmp)break;
		}
	}
}

void init() {
	memset(mp,0x3f3f3f3f,sizeof(mp));
	memset(dp,0x3f3f3f3f,sizeof(dp));
}

bool input() {
	while(scanf("%d %d",&n,&m) == 2) {
		for(int i=0;i