[bzoj2143][Dijkstra]飞飞侠

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<=10^9;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

题解

显然裸建出所有边的复杂度是N4$N^4$的
稳定炸
我们考虑把边转成点
如果在i,j点获得b[i][j]的能量，充量于能从(i,j)走b[i][j]步
设状态d[i][j][k]$d[i][j][k]$表示在i,j$i,j$点，当前有k个能量的最小步数
每次五种状态转移
上下左右以及原地不动
dij就行了….

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int dx[5]={-1,0,1,0,0};
const int dy[5]={0,-1,0,1,0};
struct pt
{
    int x,y,num;LL c;
    pt(){}
    pt(int _x,int _y,int _num,LL _c){x=_x;y=_y;num=_num;c=_c;}
    friend bool operator <(pt n1,pt n2){return n1.c>n2.c;}
};
priority_queue<pt> q;
bool v[155][155][305];
LL d[155][155][305];
int n,m,A[155][155],B[155][155];
int pox[4],poy[4];
void dij(int stx,int sty)
{
    memset(d,62,sizeof(d));memset(v,false,sizeof(v));
    d[stx][sty][0]=0;
    while(!q.empty())q.pop();
    q.push(pt(stx,sty,0,0));
    while(!q.empty()&&(!v[pox[1]][poy[1]][0]||!v[pox[2]][poy[2]][0]||!v[pox[3]][poy[3]][0]))
    {
        pt tmp=q.top();q.pop();
        if(v[tmp.x][tmp.y][tmp.num])continue;
        v[tmp.x][tmp.y][tmp.num]=true;
        if(tmp.num)
        {
            for(int i=0;i<=4;i++)
            {
                int pp=tmp.x+dx[i],qq=tmp.y+dy[i];
                if(pp<1||pp>n||qq<1||qq>m)continue;
                if(d[pp][qq][tmp.num-1]>tmp.c)
                {
                    d[pp][qq][tmp.num-1]=tmp.c;
                    q.push(pt(pp,qq,tmp.num-1,tmp.c));
                }
            }
        }
        else
        {
            int t=B[tmp.x][tmp.y];
            if(d[tmp.x][tmp.y][t]>d[tmp.x][tmp.y][0]+(LL)A[tmp.x][tmp.y])
            {
                d[tmp.x][tmp.y][t]=d[tmp.x][tmp.y][0]+(LL)A[tmp.x][tmp.y];
                q.push(pt(tmp.x,tmp.y,t,d[tmp.x][tmp.y][t]));
            }
        }
    }
}
LL sum[4][4];
int main()
{
//  freopen("2.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&B[i][j]),B[i][j]=min(B[i][j],300);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&A[i][j]); 
    for(int i=1;i<=3;i++)scanf("%d%d",&pox[i],&poy[i]);
    for(int i=1;i<=3;i++)
    {
        dij(pox[i],poy[i]);
        for(int j=1;j<=3;j++)sum[i][j]=d[pox[j]][poy[j]][0];
    }
    LL ans=(1LL<<62-1);int u=-1;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)if(i!=j)
            for(int k=1;k<=3;k++)if(k!=i&&k!=j)
            {
                if(ans>sum[j][i]+sum[k][i])ans=sum[j][i]+sum[k][i],u=i;
            }
    if(u==-1)printf("NO\n");
    else 
    {
        printf("%c\n",u+'X'-1);
        printf("%lld\n",ans);
    }
    return 0;
}