HDU 4568 Hunter 最短路+状压DP

时间：2023-03-09 20:04:03
HDU 4568 Hunter 最短路+状压DP

题意：给一个n*m的格子，格子中有一些数，如果是正整数则为到此格子的花费，如果为-1表示此格子不可到，现在给k个宝藏的地点(k<=13),求一个人从边界外一点进入整个棋盘，然后拿走所有能拿走的宝藏的最小花费，如果一次不能拿走所有能拿到的或者根本拿不到任何宝藏，输出0.

解法：看到k的范围应该想到状态压缩，将每个格子都看成一个点，再新建两个点，一个表示边界外的起点，用0表示，一个表示边界外的终点，用n*m+1表示，然后相互建边，建有向边，边权为终点格子的花费值，（其实都不用建边，直接跑最短路也行）然后求这k+2个点两两之间的最短距离，然后就化成TSP问题了，用状压DP可以解决。

求k+2个点两两之间的最短距离可以跑k+2次SPFA求出，复杂度不高。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <queue>

#include <algorithm>

#define Mod 1000000007

using namespace std;

#define N 10007

int mp[][];

int C[][];

int dis[][];

int n,m,k;

int d[];

struct node

{

    int v,w,next;

}G[*];

int head[*],tot;

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

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

int vis[];

struct Point

{

    int x,y;

}P[];

int OK(int nx,int ny)

{

    if(nx >=  && nx <= n && ny >=  && ny <= m)

        return ;

    return ;

}

void addedge(int u,int v,int w)

{

    G[tot].v = v;

    G[tot].w = w;

    G[tot].next = head[u];

    head[u] = tot++;

}

void SPFA(int s)

{

    queue<int> que;

    memset(vis,,sizeof(vis));

    que.push(s);

    for(int i=;i<=n*m+;i++) d[i] = Mod;

    d[s] = , vis[s] = ;

    while(!que.empty())

    {

        int u = que.front();

        que.pop();

        vis[u] = ;

        for(int i=head[u];i!=-;i=G[i].next)

        {

            int v = G[i].v;

            int w = G[i].w;

            if(d[v] > d[u] + w)

            {

                d[v] = d[u] + w;

                if(!vis[v])

                    vis[v] = ,que.push(v);

            }

        }

    }

}

int dp[<<][];

int main()

{

    int i,j;

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

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

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

            {

                scanf("%d",&C[i][j]);

                if(C[i][j] == -)

                    C[i][j] = Mod;

            }

        memset(head,-,sizeof(head));

        tot = ;

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

        {

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

            {

                int now = (i-)*m + j;

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

                {

                    int kx = i + dx[h];

                    int ky = j + dy[h];

                    if(!OK(kx,ky))

                        continue;

                    int tmp = (kx-)*m + ky;

                    addedge(now,tmp,C[kx][ky]);

                }

                if(i ==  || i == n || j ==  || j == m)  //边界

                {

                    addedge(,now,C[i][j]);

                    addedge(now,n*m+,);

                }

            }

        }

        scanf("%d",&k);

        P[].x = , P[].y = ;

        P[k+].x = n,P[k+].y = m+;

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

            scanf("%d%d",&P[i].x,&P[i].y),P[i].x++,P[i].y++;

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

        {

            int s = (P[i].x-)*m + P[i].y;

            SPFA(s);

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

            {

                if(i == j) continue;

                int v = (P[j].x-)*m + P[j].y;

                dis[i][j] = d[v];

            }

        }

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

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

                dp[i][j]=Mod;

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

            dp[<<i][i+]=dis[][i+];

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

        {

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

            {

                if(!(i&(<<kk)))continue;

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

                {

                    if(i&(<<j)) continue;

                    dp[i+(<<j)][j+]=min(dp[i+(<<j)][j+],dp[i][kk+]+dis[kk+][j+]);

                }

            }

        }

        int minn=Mod;

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

            minn=min(dp[(<<k)-][i]+dis[i][k+],minn);

        if(minn == Mod)

            cout<<<<endl;

        else

            cout<<minn<<endl;

    }

    return ;

}

相关文章