hdu 5418 (Floyd+哈密顿) 飞向世界

http://acm.hdu.edu.cn/showproblem.php?pid=5418

题目大意是城市的编号是1到n,给出m条路线,表示从a城市飞到b城市飞机要耗多少油,最后问飞机从1出发飞过所有的的城市最后再回到1最少耗多少油(数据保证至少存在一条这样的路),

要考虑的问题是满足全部连通和保证最短,最短好说,用弗洛伊德或者迪杰特斯拉,至于这个全部连通,一下子连想到了之前的状压搜索,用二进制保存是否经过所有的点,最后整理一下就是先

用弗洛伊德求出每从起点1到各个点的最短距离,然后哈密顿算法进行全连通,找出最小的油耗

code

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define inf 0x3f3f3f3f

 using namespace std;

 int min(int x,int y)

 {

     if (x<y) return x;

     else return y;

 }

 int map[][],dis[][<<];

 int main()

 {

     int t,m,i,j,a,b,c,k,mn,ans,n;

     while (~scanf("%d",&t))

     {

         while (t--)

         {

             scanf("%d %d",&n,&m);

             for (i=;i<=n;i++)

             {

                 for (j=;j<=n;j++)

                 {

                     map[i][j]=inf;

                     if (i==j) map[i][j]=;

                 }

             }

             while (m--)

             {

                 scanf("%d %d %d",&a,&b,&c);

                 if (map[a][b]>c)

                    map[a][b]=map[b][a]=c;

             }

             for (k=;k<=n;k++){ //最短路

                for (i=;i<=n;i++){

                    for (j=;j<=n;j++)

                       map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

                }

             }

             memset(dis,inf,sizeof(dis));

             dis[][]=;

             for (i=;i<(<<n);i++){

                for (j=;j<=n;j++){

                    if ((i&(<<(j-)))!=){

                       for (k=;k<=n;k++)

                       {

                           if ((i&(<<(k-)))==){

                               ans=(i|(<<(k-)));

                               dis[k][ans]=min(dis[k][ans],dis[j][i]+map[j][k]);

                           }

                       }

                    }

                }

             }

             if (n==)

             {

                 printf("0\n");

                 continue;

             }

             mn=inf;

             for (i=;i<=n;i++)

                mn=min(mn,dis[i][(<<n)-]+map[][i]);

             printf("%d\n",mn);

         }

     }

     return ;

 }