poj3311
我写的第一篇状压dp，调试了好久23333，其实状压就是二进制结合位运算，把整体的状态用二进制来表示，一般是0/1，用没用过或者走没走没走过的问题，其实这种思想在搜索中也有涉及过，与dp结合灵活度较高。状态占1维，还有其他维。
这个题就是f[i][j]表示，i状态下，当前在j位置的最短距离，转移过程与floyed相似。第一次尝试就掉坑（痛苦的体验啊
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 #include<cmath> 6 #include<ctime> 7 #include<set> 8 #include<map> 9 #include<stack> 10 #include<cstring> 11 #define inf 2147483647 12 #define ls rt<<1 13 #define rs rt<<1|1 14 #define lson ls,nl,mid,l,r 15 #define rson rs,mid+1,nr,l,r 16 #define N 100010 17 #define For(i,a,b) for(long long i=a;i<=b;i++) 18 #define p(a) putchar(a) 19 #define g() getchar() 20 21 using namespace std; 22 long long n; 23 long long dis[20][20],m[20][20]; 24 long long f[1<<12][20]; 25 void in(long long &x){ 26 long long y=1; 27 char c=g();x=0; 28 while(c<'0'||c>'9'){ 29 if(c=='-')y=-1; 30 c=g(); 31 } 32 while(c<='9'&&c>='0'){ 33 x=(x<<1)+(x<<3)+c-'0';c=g(); 34 } 35 x*=y; 36 } 37 void o(long long x){ 38 if(x<0){ 39 p('-'); 40 x=-x; 41 } 42 if(x>9)o(x/10); 43 p(x%10+'0'); 44 } 45 int main(){ 46 while(cin>>n&&n){ 47 48 For(i,0,n) 49 For(j,0,n){ 50 in(m[i][j]); 51 dis[i][j]=m[i][j]; 52 } 53 54 55 For(i,0,n) 56 For(j,0,n) 57 For(k,0,n) 58 if(dis[i][j]>dis[i][k]+m[k][j]) 59 dis[i][j]=dis[i][k]+m[k][j]; 60 61 memset(f,-1,sizeof(f)); 62 f[1][0]=0; 63 64 For(i,1,(1<<(n+1))-1){ 65 i=i|1; 66 For(j,0,n){ 67 if(f[i][j]!=-1) 68 For(k,0,n) 69 if((j!=k)&&(f[(1<<k)|i][k]==-1||f[(1<<k)|i][k]>f[i][j]+dis[j][k])) 70 f[(1<<k)|i][k]=f[i][j]+dis[j][k]; 71 72 73 } 74 75 } 76 o(f[(1<<(n+1))-1][0]); 77 p(' '); 78 } 79 return 0; 80 }