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

2143: 飞飞侠 最短路

程序员文章站 2022-05-22 13:35:03
...

Description
飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵,每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么,任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图 (从红色街区交费以后可以跳到周围的任意蓝色街区。) 现在的问题很简单。有三个飞飞侠,分别叫做X,Y,Z。现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标,求往哪里集合大家需要花的费用总和最低。

题解:

直接最短路的话边数巨大,考虑转变状态表示f[i][j][k]表示到达(i,j)还能免费走k次的最小花费,直接转移即可,复杂度O(n3logn3)

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,S>
const int Maxn=155;
const LL inf=4557430888798830399ll;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
bool vis[Maxn][Maxn][Maxn<<1];
int A[Maxn][Maxn],n,m;
LL B[Maxn][Maxn];
struct P{int x,y;}p[4];
struct S{int x,y,k;};
bool operator < (S a,S b){return a.x<b.x;}
LL f[Maxn][Maxn][Maxn<<1];
bool in(int x,int y){return(x>0&&y>0&&x<=n&&y<=m);}
int tx[]={0,0,1,-1};
int ty[]={1,-1,0,0};
void dijkstra(int x,int y)
{
    memset(vis,false,sizeof(vis));
    memset(f,63,sizeof(f));f[x][y][0]=0;
    priority_queue<pa,vector<pa >, greater<pa > >q;
    S s;s.x=x;s.y=y;s.k=0;
    q.push(make_pair(0,s));
    while(!q.empty()&&!(vis[p[1].x][p[1].y][0]&&vis[p[2].x][p[2].y][0]&&vis[p[3].x][p[3].y][0]))
    {
        pa t=q.top();q.pop();
        S tmp=t.second;
        int x=tmp.x,y=tmp.y,k=tmp.k;
        if(vis[x][y][k])continue;
        vis[x][y][k]=true;
        if(k)
        {
            for(int i=0;i<4;i++)
            {
                int nx=x+tx[i],ny=y+ty[i];
                if(in(nx,ny))
                {
                    if(f[x][y][k]<f[nx][ny][k-1])
                    {
                        f[nx][ny][k-1]=f[x][y][k];
                        S o;o.x=nx;o.y=ny;o.k=k-1;
                        q.push(make_pair(f[nx][ny][k-1],o));
                    }
                }
            }
            if(f[x][y][k]<f[x][y][k-1])f[x][y][k-1]=f[x][y][k],tmp.k--,q.push(make_pair(f[x][y][k],tmp));
        }
        if(f[x][y][k]+B[x][y]<f[x][y][A[x][y]])
        {
            f[x][y][A[x][y]]=f[x][y][k]+B[x][y];
            S o;o.x=x;o.y=y;o.k=A[x][y];
            q.push(make_pair(f[x][y][A[x][y]],o));
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    A[i][j]=min(read(),max(i-1,n-i)+max(j-1,m-j));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    B[i][j]=read();
    for(int i=1;i<=3;i++)p[i].x=read(),p[i].y=read();
    LL ans=inf,t12,t13,t21,t23,t31,t32;int w;
    dijkstra(p[1].x,p[1].y);
    t12=f[p[2].x][p[2].y][0],t13=f[p[3].x][p[3].y][0];
    dijkstra(p[2].x,p[2].y);
    t21=f[p[1].x][p[1].y][0],t23=f[p[3].x][p[3].y][0];
    dijkstra(p[3].x,p[3].y);
    t32=f[p[2].x][p[2].y][0],t31=f[p[1].x][p[1].y][0];
    if(t21+t31<ans)ans=t21+t31,w=1;
    if(t12+t32<ans)ans=t12+t32,w=2;
    if(t13+t23<ans)ans=t13+t23,w=3;
    if(ans==inf)puts("NO");
    else
    {
        if(w==1)puts("X");
        else if(w==2)puts("Y");
        else puts("Z");
        printf("%lld",ans);
    }
}