HDU 4856 (状态压缩DP+TSP)

时间：2022-01-11 16:55:15

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4856

题目大意：有一个迷宫。迷宫里有些隧道，每个隧道有起点和终点，在隧道里不耗时。出隧道就耗时，你的任务是访问完所有隧道且仅一次，求最短耗时。

解题思路：

暑假练习的时候。把英文读了N遍也没理解题意。

其实就是个最后不回到开头的TSP。

首先求BFS求两两隧道之间的最短路，注意BFS的起点是隧道i的终点，BFS的终点是隧道j的起点。

一定要特判一下两个隧道终点和起点是否一样，如果一样话dis=0, 我因为BFS没注意这个WA了10几次。

PS. 根据esxgx大神的说法，所有最短路算法(Dijkstra or Bellman-Ford)在每两个点距离为1的时候都会退化成普通的BFS，于是你在这里相当于手艹了个最短路。

然后就是对所有隧道进行TSP。

dp[i][j]表示状态i时，在j点的最少耗时，然后就是赤裸裸的TSP了。TSP的写法不唯一，我从别人那扒的这种TSP稍微快点。

#include "cstdio"

#include "string"

#include "iostream"

#include "cstring"

#include "queue"

#include "vector"

using namespace std;

int n,m,vis[][],dis[][],dir[][]={-,,,,,-,,},ans,dp[<<][];

char map[][];

const int inf=0x3f3f3f3f;

struct status

{

    int x,y,dep;

    status(int x,int y,int dep):x(x),y(y),dep(dep) {}

};

struct tunnel

{

    int sx,sy,ex,ey;

}T[];

int bfs(status a,status b)

{

    if(a.x==b.x&&a.y==b.y) return ; //关键一步,如果两个隧道恰好拼在一起，则dis=0

    memset(vis,,sizeof(vis));

    int ans=inf;

    queue<status> Q;

    Q.push(a);

    vis[a.x][a.y]=true;

    while(!Q.empty())

    {

        status t=Q.front();Q.pop();

        for(int s=;s<;s++)

        {

            int X=t.x+dir[s][],Y=t.y+dir[s][];

            if(X<||X>n||Y<||Y>n||vis[X][Y]||map[X][Y]!='.') continue;

            vis[X][Y]=true;

            if(X==b.x&&Y==b.y) {ans=min(ans,t.dep+);return ans;}

            Q.push(status(X,Y,t.dep+));

        }

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio(false);

    string tt;

    while(cin>>n>>m)

    {

        memset(dis,,sizeof(dis));

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

        {

            cin>>tt;

            for(int j=;j<tt.size();j++) map[i][j+]=tt[j];

        }

        for(int i=;i<=m;i++)

            cin>>T[i].sx>>T[i].sy>>T[i].ex>>T[i].ey;

        for(int i=;i<=m;i++)

            for(int j=;j<=m;j++)

        {

            if(i==j) {dis[i][j]=;}

            else dis[i][j]=bfs(status(T[i].ex,T[i].ey,),status(T[j].sx,T[j].sy,));

        }

        int cnt=<<m,res=inf;

        for(int i=;i<cnt;i++)

        {

            for(int j=;j<=m;j++)

            {

                int s=(<<(j-));

                if((i&s)==) continue;

                if(i==s) dp[i][j]=;

                else dp[i][j]=inf;

                for(int k=;k<=m;k++)

                {

                    int t=(<<(k-));

                    if((i&t)==||k==j||dis[k][j]==inf) continue;

                    dp[i][j]=min(dp[i][j],dp[i^s][k]+dis[k][j]);

                }

                if(i==cnt-) res=min(res,dp[i][j]);

            }

        }

        if(res==inf) printf("-1\n");

        else printf("%d\n",res);

    }

}
11887989 2014-10-16 20:17:15 Accepted 4856 171MS 2852K 2290 B C++ Physcal

相关文章