BZOJ 2143 飞飞侠（最短路变形）

程序员文章站 2022-05-22 13:38:44

...

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

Input:
　输入的第一行包含两个整数N和M，分别表示行数和列数。接下来是2个N×M的自然数矩阵，为Aij和Bij 最后一行六个数，分别代表X，Y，Z所在地的行号和列号。

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

数据范围：
1<=N,M<=200,0<=Bi<=109,0<=Ai<=1000;

题解：
　首先这肯定是一道最短路的题；
　但是由于数据范围的限制，直接建边是不可能的；
　我们考虑这道题的特殊性，将弹射距离，转化为在地图中可以走这么多步，而不消耗费用。所以我们考虑用 dis[ i ][ j ][ k ]表示在（i , j）这个点，当前还能走Ｋ步的最小代价，就避免了建边，从而得到答案。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<cctype>
#include<queue>
using namespace std;
const int INF = 100000000;
const int N = 205;
const int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int len,n,m,x1,x2,x3,yy1,y2,y3,t1,t2,t3;
int a[N][N],b[N][N],dis[N][N][N*2];
bool vis[N][N][N*2];
struct node{int x,y,z,d;};
bool operator <(const node&a,const node&b){ return a.d>b.d;}
inline int Readint(){
    int i=0;char c;
    for(c=getchar();!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar()) i=(i<<1)+(i<<3)+c-'0';
    return i;
}

inline void solve(int sx,int sy){
    priority_queue< node >  q;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        for(int k=0;k<=len;k++)
          dis[i][j][k]=INF,vis[i][j][k]=0;
    dis[sx][sy][0]=0;
    node u,v;u.x=sx;u.y=sy;u.z=u.d=0;q.push(u);
    while(!q.empty() && !(vis[x1][yy1][0] && vis[x2][y2][0] && vis[x3][y3][0])){
        u=q.top();q.pop();
        if(vis[u.x][u.y][u.z]) continue;vis[u.x][u.y][u.z]=true;
        if(u.z){
            for(int k=0;k<4;k++){
                int fx=u.x+dx[k];int fy=u.y+dy[k];
                if(fx>0&&fx<=n&&fy>0&&fy<=m&&u.d<dis[fx][fy][u.z-1]){
                    dis[fx][fy][u.z-1]=v.d=u.d;
                    v.x=fx;v.y=fy;v.z=u.z-1;q.push(v);
                }
            }
            v=u;v.z--;
            if (v.d<dis[v.x][v.y][v.z]){ dis[v.x][v.y][v.z]=v.d; q.push(v); }
        }
        else{
            v=u;v.z=a[v.x][v.y];v.d+=b[v.x][v.y];
            if(v.d<dis[v.x][v.y][v.z]) dis[v.x][v.y][v.z]=v.d,q.push(v); 
        }
    }
}

int main(){
    //freopen("lx.in","r",stdin);

    n=Readint(),m=Readint();
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++){
        a[i][j]=Readint();a[i][j]=min(a[i][j],max(i-1,n-i)+max(j-1,m-j)+1);
        len=max(len,a[i][j]);
      }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++) b[i][j]=Readint();
    x1=Readint(),yy1=Readint(),x2=Readint(),y2=Readint(),x3=Readint(),y3=Readint();
    solve(x1,yy1);t2+=dis[x2][y2][0];t3+=dis[x3][y3][0];
    solve(x2,y2);t1+=dis[x1][yy1][0];t3+=dis[x3][y3][0];
    solve(x3,y3);t1+=dis[x1][yy1][0];t2+=dis[x2][y2][0];
    int ans=min(t1,min(t2,t3));
    if(ans<INF){
        puts((ans==t1)?"X":(ans==t2)?"Y":"Z");
        cout<<ans;
    }else puts("NO");
}

上一篇： [BZOJ2143]飞飞侠并查集优化最短路

下一篇：唐朝公主和高僧的禁忌之恋，最终是什么结果？

BZOJ 2143 飞飞侠（最短路变形）