poj3311

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

poj3311
我写的第一篇状压dp，调试了好久23333，其实状压就是二进制结合位运算，把整体的状态用二进制来表示，一般是0/1，用没用过或者走没走没走过的问题，其实这种思想在搜索中也有涉及过，与dp结合灵活度较高。状态占1维，还有其他维。
这个题就是f[i][j]表示，i状态下，当前在j位置的最短距离，转移过程与floyed相似。第一次尝试就掉坑（痛苦的体验啊

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define ls rt<<1

 #define rs rt<<1|1

 #define lson ls,nl,mid,l,r

 #define rson rs,mid+1,nr,l,r

 #define N 100010

 #define For(i,a,b) for(long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 using namespace std;

 long long n;

 long long dis[][],m[][];

 long long f[<<][];

 void in(long long &x){

     long long y=;

     char c=g();x=;

     while(c<''||c>''){

         if(c=='-')y=-;

         c=g();

     }

     while(c<=''&&c>=''){

         x=(x<<)+(x<<)+c-'';c=g();

     }

     x*=y;

 }

 void o(long long x){

     if(x<){

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 int main(){

     while(cin>>n&&n){

     For(i,,n)

       For(j,,n){

           in(m[i][j]);

           dis[i][j]=m[i][j];

       }

     For(i,,n)

         For(j,,n)

             For(k,,n)

                 if(dis[i][j]>dis[i][k]+m[k][j])

                     dis[i][j]=dis[i][k]+m[k][j];

     memset(f,-,sizeof(f));

     f[][]=;

     For(i,,(<<(n+))-){

         i=i|;

         For(j,,n){

             if(f[i][j]!=-)

             For(k,,n)

                 if((j!=k)&&(f[(<<k)|i][k]==-||f[(<<k)|i][k]>f[i][j]+dis[j][k]))

                     f[(<<k)|i][k]=f[i][j]+dis[j][k];

         }

     }

     o(f[(<<(n+))-][]);

     p('\n');

 }

     return ;

 }