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

bzoj2143: 飞飞侠(最短路)

程序员文章站 2022-05-22 13:57:55
...

2143: 飞飞侠

Time Limit: 50 Sec
Memory Limit: 259 MB

Description

飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵,每个格子代表一个街区。然
而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需
要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹
射能力。并规定有相邻边的格子间距离是1。那么,任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹
到距离不超过Bij的位置了。如下图

(从红色街区交费以后可以跳到周围的任意蓝色街区。)现在的问题很简单。有三个飞飞侠,分别叫做X,Y,Z。
现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标,求往哪里集合大家需要花的
费用总和最低。

Input

输入的第一行包含两个整数N和M,分别表示行数和列数。
接下来是2个N×M的自然数矩阵,为Aij和Bij
最后一行六个数,分别代表X,Y,Z所在地的行号和列号。
1<=N,M<=150;0<=Aij<=109;0<=Bij<=1000

Output

第一行输出一个字符X、Y或者Z。表示最优集合地点。
第二行输出一个整数,表示最小费用。如果无法集合,只输出一行NO

Sample Input

4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2

Sample Output

Z
15










解:

黄学长的代码似乎wa了,有两个人在同一个点上时就凉了。
但是想法是对的,我们点比较少,所以拆点。我们想到花费其实是给自己加油,然后花一点油可以走到旁边。我们拆点,(i,j,k)表示到i,j坐标还剩k点油的最短路。然后每种状态就只会有5种连边。跑三遍最短路即可。
细节上为什么(x,y,0)被打标记就结束?其实好像只要(x,y,_)中有一个打上标记就可以结束,因为dj最短路一定近的点先打标记,所以先出堆的一定是最短的。当时没有想清楚,所以写的有点傻。还有就是一定要退出,不然特别慢,根本不像一个复杂度。被dj制裁了,好久没写过了。
code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct lxy{
    int x,y,k;
    long long dis;
    bool operator < (const lxy &QAQ)const{
      return dis>QAQ.dis;
    }
}yyy;
int n,m;
int a[155][155];
int b[155][155];
long long dis[155][155][305],ans=0x3f3f3f3f3f3f3f3f,len[5][5];
int g[155][155];
bool vis[155][155][305];
int x1,y1,x2,y2,x3,y3,fg;
priority_queue <lxy> d;

void addans()
{
    for(int i=0;i<=300;i++)
      len[fg][1]=min(len[fg][1],dis[x1][y1][i]);
    for(int i=0;i<=300;i++)
      len[fg][2]=min(len[fg][2],dis[x2][y2][i]);
    for(int i=0;i<=300;i++)
      len[fg][3]=min(len[fg][3],dis[x3][y3][i]);
}

void spfa(int x,int y)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[x][y][0]=0;yyy.x=x;yyy.y=y;yyy.k=0;yyy.dis=0;d.push(yyy);
    while(!d.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0])){
        lxy now=d.top();
        vis[now.x][now.y][now.k]=1;d.pop();
        if(dis[now.x][now.y][g[now.x][now.y]]>dis[now.x][now.y][now.k]+a[now.x][now.y]){
            dis[now.x][now.y][g[now.x][now.y]]=dis[now.x][now.y][now.k]+a[now.x][now.y];
            yyy.x=now.x;yyy.y=now.y;yyy.k=g[now.x][now.y];yyy.dis=dis[now.x][now.y][g[now.x][now.y]];d.push(yyy);
        }
        if(now.x<n&&now.k!=0){
            if(dis[now.x+1][now.y][now.k-1]>dis[now.x][now.y][now.k]){
                dis[now.x+1][now.y][now.k-1]=dis[now.x][now.y][now.k];
                yyy.x=now.x+1;yyy.y=now.y;yyy.k=now.k-1;yyy.dis=dis[now.x+1][now.y][now.k-1];d.push(yyy);
            }
        }
        if(now.y<m&&now.k!=0){
            if(dis[now.x][now.y+1][now.k-1]>dis[now.x][now.y][now.k]){
                dis[now.x][now.y+1][now.k-1]=dis[now.x][now.y][now.k];
                yyy.x=now.x;yyy.y=now.y+1;yyy.k=now.k-1;yyy.dis=dis[now.x][now.y+1][now.k-1];d.push(yyy);
            }
        }
        if(now.x>1&&now.k!=0){
            if(dis[now.x-1][now.y][now.k-1]>dis[now.x][now.y][now.k]){
                dis[now.x-1][now.y][now.k-1]=dis[now.x][now.y][now.k];
                yyy.x=now.x-1;yyy.y=now.y;yyy.k=now.k-1;yyy.dis=dis[now.x-1][now.y][now.k-1];d.push(yyy);
            }
        }
        if(now.y>1&&now.k!=0){
            if(dis[now.x][now.y-1][now.k-1]>dis[now.x][now.y][now.k]){
                dis[now.x][now.y-1][now.k-1]=dis[now.x][now.y][now.k];
                yyy.x=now.x;yyy.y=now.y-1;yyy.k=now.k-1;yyy.dis=dis[now.x][now.y-1][now.k-1];d.push(yyy);
            }
        }
        while(!d.empty()&&vis[d.top().x][d.top().y][d.top().k]==1) d.pop();
    }
    while(!d.empty())d.pop();
    addans();
}

int main()
{
    memset(len,0x3f,sizeof(len));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%d",&b[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        g[i][j]=min(b[i][j],max(i-1,n-i)+max(j-1,m-j));
    scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
    fg=1;spfa(x1,y1);
    fg=2;spfa(x2,y2);
    fg=3;spfa(x3,y3);
    fg=0;
    for(int i=1;i<=3;i++)
    {
        long long t=0;
        for(int j=1;j<=3;j++)
          t+=len[j][i];
        if(t<ans) ans=t,fg=i;
    }
    if(fg==0) printf("NO");
    if(fg==1) printf("X\n%lld",ans);
    if(fg==2) printf("Y\n%lld",ans);
    if(fg==3) printf("Z\n%lld",ans);
}