HDU-4568 TSP+最短路

题意：给一个n行m列的矩阵，矩阵上的数字代表经过代价（这里要注意每经过一次都要付出代价），矩阵上有几个宝藏，猎人可以从任意边界进去矩阵取完所有宝藏后从任意边界出来。

解法：一看到宝藏数量小于等于13且必须经过，应该很容易想到TSP问题。所以我们用最短路预处理+状态压缩DP解决。首先预处理所有宝藏点到整个地图的最短路这是为了后续的dp代价做准备，然后开始状压dp，设计dp状态为dp[S][now]代表现在去了的宝藏点集为S且现在在now宝藏点的最小值，用记忆化搜索转移即可。

细节详见代码，应该挺好懂的：

#include<bits/stdc++.h>

using namespace std;

const int N=;

const int INF=0x3f3f3f3f;

const int dx[]={-,,,};

const int dy[]={,,,-};

int n,m,k,a[N][N],dp[<<][],es[N],px[N],py[N];

struct dat{

    int d,x,y;

    bool operator < (const dat &rhs) const {

        return d>rhs.d;

    }

};

priority_queue<dat> q;

int dis[][N][N];

bool vis[N][N];

void Dijkstra(int k) {

    memset(dis[k],0x3f,sizeof(dis[k]));

    memset(vis,,sizeof(vis));

    q.push((dat){,px[k],py[k]});

    dis[k][px[k]][py[k]]=;

    while (!q.empty()) {

        dat u=q.top(); q.pop();

        if (vis[u.x][u.y]) continue;

        vis[u.x][u.y]=;

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

            int tx=u.x+dx[i],ty=u.y+dy[i];

            if (tx< || tx>n || ty< || ty>m || a[tx][ty]==-) continue;

            if (dis[k][tx][ty]>dis[k][u.x][u.y]+a[tx][ty]) {

                dis[k][tx][ty]=dis[k][u.x][u.y]+a[tx][ty];

                q.push((dat){dis[k][tx][ty],tx,ty});

            }

        }

    }

}

int lowbit(int x) { int ret=; for (;x;x-=x&-x) ret++; return ret; }

int dfs(int now,int x) {

    if (dp[now][x]!=-) return dp[now][x];

    if (lowbit(now)==) return es[x]+a[px[x]][py[x]];

    dp[now][x]=INF;

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

        if ((i!=x) && (now&(<<i-))) {

            int tmp=dfs(now^(<<x-),i)+dis[i][px[x]][py[x]];

            dp[now][x]=min(dp[now][x],tmp);

    }

    return dp[now][x];

}

int main()

{

    int T; cin>>T;

    while (T--) {

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

        for (int i=;i<=n;i++) for (int j=;j<=m;j++) scanf("%d",&a[i][j]);

        scanf("%d",&k);

        for (int i=;i<=k;i++) {

            scanf("%d%d",&px[i],&py[i]);

            px[i]++; py[i]++;

            Dijkstra(i);

            es[i]=INF;

            for (int j=;j<=n;j++) es[i]=min(es[i],min(dis[i][j][],dis[i][j][m]));

            for (int j=;j<=m;j++) es[i]=min(es[i],min(dis[i][][j],dis[i][n][j]));

        }

        memset(dp,-,sizeof(dp));

        int ans=INF;

        for (int i=;i<=k;i++) ans=min(ans,dfs((<<k)-,i)+es[i]);

        if (ans==INF) printf("-1"); else printf("%d\n",ans);

    }

    return ;

}

巴特西

HDU-4568 TSP+最短路

最新文章

热门文章