有道状压题用了搜索被队友骂还能不能好好训练了，，
hdu 3001 经典的状压dp
大概题意。。有n个城市 m个道路 成了一个有向图。n<=10； 然后这个人想去旅行。有个超人开始可以把他扔到任意的一个城市。。然后他就在城市之间游荡。要满足他要游玩所有的城市。。并且。每个城市最多去两次。要求路程最短。。如果他不能游完所有的城市，，那么。。就输出-1 否则 输出最短距离
如果用搜索。。。不靠谱 然后用搜索，，
怎么压缩？？ 用一个整型数 i 表示他现在的状态。。显然一个城市是要用两位。。00 表示没去过 01 表示去了一次 10 表示去了两次 然后最多10个城市，。。那么一共用20位 2^20一共是。。1024*1024 也就是10^6大概吧。。 然后dp[i][j] 表示的是 当前这个状态。。并且 最后他在j城市的最短路径。。然后他可以去另外的城市 咋一看 这个时间复杂度是 。。10^6 * 10 * 10 然后加上各种判断。。还要开一个10^6 *10 的数组 然后就MLE 了，，我们发现 i 在自然数里面并不是连续的 而是离散的 我们 先找出满足条件的 i 存在一个数组inn里面 然后用二分查找 。。。相当于用了一个哈希表，，存了这么多的情况，，，然后就是dp转移了，，，，
MLE 1 wa1 : 没考虑输出-1 的情况
代码不长
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <cstring>
#define CL(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define TEST cout<<"TEST ***"<<endl;
#define INF 0x7ffffff0
#define MOD 100000000
using namespace std; int inn[];
int dp[][];
int gra[][];
int n,m,cii; int bin(int s,int e,int v)
{
int mid=(s+e)/;
if(inn[mid]==v)return mid;
if(inn[mid]>v)return bin(s,mid,v);
else return bin(mid+,e,v);
} int initinn()
{
int i,ctt=,taginn,teminn;
for(i=;i<=;i++)
{
teminn=i;taginn=;
while(teminn)
{
if((teminn&)==)
{
taginn=;
break;
}
teminn=teminn>>;
}
if(taginn==)
{
inn[ctt++]=i;
}
}
return ctt;
} int main()
{
cii=initinn();
while(scanf("%d %d",&n,&m)!=EOF)
{
CL(gra,-);
int i,j,k,a,b,w;
int rem=INF;
int ma=(<<(*n))-;
for(i=;i<m;i++)
{
scanf("%d %d %d",&a,&b,&w);
if(gra[a][b]==-||gra[a][b]>w)
{
gra[a][b]=gra[b][a]=w;
}
} CL(dp,-);
for(i=;i<=n;i++)dp[][i]=;
for(i=;i<=n;i++)gra[][i]=gra[i][]=gra[i][i]=;
for(i=;inn[i]<=ma;i++)
{
a=inn[i];
for(j=;j<=n;j++)
{
if(dp[i][j]==-)continue;
for(k=;k<=n;k++)
{
if(gra[j][k]==-)continue;
b=k-;
if(a&(<<(*b+)))continue;
w=a+(<<(*b));
w=bin(,cii,w);
if(dp[w][k]==-||dp[w][k]>dp[i][j]+gra[j][k])
dp[w][k]=dp[i][j]+gra[j][k];
}
b=; w=a;
for(k=;k<=n;k++)
{
if((w&)==)
{
b=;
break;
}
w=w>>;
}
if(b==&&dp[i][j]<rem)rem=dp[i][j];
}
}
if(rem==INF)rem=-;
printf("%d\n",rem);
}
return ;
}