欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj 2143 飞飞侠【最短路】

程序员文章站 2022-05-22 13:34:45
...

解题思路:

这道题点很少,但是边可能很多,直接建图做最短路显然不可行。
但是如果把弹射看成获得了可以走a[i][j]的能量。
这样就可以直接最短路了。
每走一格可看作消耗1的能量,f[i][j][k]表示在i,j这个点且有k的能量的最少费用。
每次只要向四个方向走,或者原地不动即可。
做三次最短路即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-1,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

const int N=205;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={1,0,-1,0,0};
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,H,X[4],Y[4];
int a[N][N],b[N][N];
ll dis[N][N][N<<1],D[4][4];
struct node
{
    int d,x,y,h;
    friend inline bool operator >(const node &a,const node &b)
    {
        return a.d>b.d;
    }
};
priority_queue<node,vector<node>,greater<node> >q;

void dijkstra(int S,int T1,int T2)
{
    int x,y,d,h;
    bool bz1=false,bz2=false;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<=H;k++)
                dis[i][j][k]=INF;
    while(!q.empty())q.pop();
    x=X[S],y=Y[S];
    dis[x][y][a[x][y]]=b[x][y];
    q.push((node){b[x][y],x,y,a[x][y]});
    while(!q.empty())
    {
        x=q.top().x,y=q.top().y,d=q.top().d,h=q.top().h;
        q.pop();
        if(x==X[T1]&&y==Y[T1]&&!h)
            D[S][T1]=d,bz1=true;
        if(x==X[T2]&&y==Y[T2]&&!h)
            D[S][T2]=d,bz2=true;
        if(bz1&&bz2)return;
        if(h>0)
        {
            for(int i=0;i<5;i++)
            {
                int dx=x+fx[i],dy=y+fy[i];
                if(dx<1||dx>n||dy<1||dy>m)continue;
                if(dis[dx][dy][h-1]>d)
                {
                    dis[dx][dy][h-1]=d;
                    q.push((node){d,dx,dy,h-1});
                }
            }
        }
        else
        {
            h=a[x][y];
            if(dis[x][y][h]>d+b[x][y])
            {
                dis[x][y][h]=d+b[x][y];
                q.push((node){dis[x][y][h],x,y,h});
            }
        }
    }
}

int main()
{
    //freopen("friend.in","r",stdin);
    //freopen("friend.out","w",stdout);
    n=getint(),m=getint();
    H=n+m-2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=min(getint(),H);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=getint();
    X[1]=getint(),Y[1]=getint();
    X[2]=getint(),Y[2]=getint();
    X[3]=getint(),Y[3]=getint();
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            D[i][j]=INF;
    dijkstra(1,2,3);
    dijkstra(2,1,3);
    dijkstra(3,1,2);
    ll ans=INF;char p;
    if(D[2][1]+D[3][1]<ans)ans=D[2][1]+D[3][1],p='X';
    if(D[1][2]+D[3][2]<ans)ans=D[1][2]+D[3][2],p='Y';
    if(D[1][3]+D[2][3]<ans)ans=D[1][3]+D[2][3],p='Z';
    if(ans==INF)puts("NO");
    else cout<<p<<'\n'<<ans;
    return 0;
}