hdu 3001记忆化错在哪里了？
这题的题意很简单，就是有n个城市,m条道路，你可以从任何一个城市出发，要经过所有的城市，并且每个城市最多经过两次，求最短路径。其中，你可以直接飞到起点而不需要花时间，也就是说从任何起点出发的距离是0.如果不能到达所有的城市输出-1.
我知道这题可以用状态压缩dp来写，也写出状态转移方程了，但不是很清楚递推顺序，看了网上的代码，大多都是一样的，所以打算用记忆化来写。但结果不对，生成了一些随机数据，和ac的代码比较了下，发现我的结果全是0，而ac代码不是。改了好长时间也没改对，还请大牛们帮忙看看。
下面是代码：
#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 12
#define MAXSTATUS 60000
#define INF 0X7ffffff
using namespace std;
int parent[MAXN];//used for check connectivity.
int dist[MAXN][MAXN];//dist[a][b]:the minimum distance between city a and city b.
int fac[MAXN];//fac[i]=3^i;
vector<int> status[MAXSTATUS*3];//status[i][j] stands for the jth number of state i.
int dp[MAXSTATUS*3][MAXN];
int min(int a,int b);
void prepare();
void init(int n);
int find(int x);
void search(int state,int cur,int n);
void solve(int n);
int main(){
int n,m;
/*
freopen("3001.in","r",stdin);
freopen("3001.out","w",stdout);
//*/
prepare();
while(~scanf("%d%d",&n,&m)){
init(n);
for(int i=1;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int fa=find(a),fb=find(b);
if(fa!=fb)
parent[fa]=fb;
if(dist[a][b]>c)
dist[a][b]=dist[b][a]=c;
}
int cnt=0;//check connectivity
for(int i=1;i<=n;++i){
if(parent[i]==i)
++cnt;
}
if(cnt>=2){//doesn't connected ,-1.
printf("-1\n");
continue;
}
solve(n+1);
}
return 0;
}
void prepare(){
fac[0]=1;
for(int i=1;i<=10;++i){//fac[i]=3^i;
fac[i]=3*fac[i-1];
}
for(int i=1;i<3*MAXSTATUS;++i){
int tmp=i;
while(tmp){
status[i].push_back(tmp%3);
tmp/=3;
}
}
}
int min(int a,int b){
return a<b?a:b;
}
int find(int x){
return x==parent[x]?x:find(parent[x]);
}
void init(int n){
for(int i=1;i<=n;++i){
dist[i][i]=0;
dist[0][i]=dist[i][0]=0;
parent[i]=i;
for(int j=i+1;j<=n;++j){
dist[i][j]=dist[j][i]=INF;
}
}
}
//dp[S][i]=min{dp[S-j][j]+dist[j][i]};in dp[S][i], state S doesn't include i.
void solve(int n){
const int all=fac[n]-3;
int ans=INF;
memset(dp,-1,sizeof(dp));
search(all,0,n);
if(ans>dp[all][0]){
ans=dp[all][0];
}
printf("%d\n",ans);
}
void search(int state,int cur,int n){
if(state<3 || state==fac[cur]){
dp[state][cur]=0;
return ;
}
if(dp[state][cur]!=-1)
return ;
int ans=INF;
int d=status[state].size();
for(int i=0;i<n && i<d;++i){
int aux=status[state].at(i);
if(aux>0){
int tmp=state-fac[i];
search(tmp,i,n);
if(ans>dp[tmp][i]+dist[i][cur]){
ans=dp[tmp][i]+dist[i][cur];
}
}
}
dp[state][cur]=ans;
}
#include <stdio.h>
#include <stdlib.h>
int main(){
FILE *fout=fopen("3001.in","wb");
int n,m,k,i,j,t,a,b,c;
srand(time(NULL));
for(k=1;k<=10;++k){
n=10,m=450;
fprintf(fout,"%d %d\n",n,m);
for(i=1;i<=10;++i){
for(j=1;j<=n;++j){
for(t=j+1;t<=n;++t){
a=j,b=t;
c=(rand()%1000)+10;
fprintf(fout,"%d %d %d\n",a,b,c);
}
}
}
fprintf(fout,"\n");
}
fclose(fout);
return 0;
}
