题解 P4473 【[国家集训队]飞飞侠】

一看题目，二话不说，大力线段树。

注意到如果你直接暴力连边的话边数会特别大，所以考虑用线段树。

这样说有点生硬，还是丢一副图吧。

比如，你要将上面的节点向下方的七个节点连边，直接暴力是这样的：

这样一次连边的时间复杂度是O(n)的。

而经过线段树优化后的连边是这样的：

这样一次连边的时间复杂度就变成了O(\log n)。虽然图上的边数要比暴力多一些，但下面的边都是线段树的一部分，是O(n)的，对总体的边数不会有太大的影响。

现在考虑这一道题。每一个点要连的边是一个连通块：

所以就从上到下枚举每一行，在每一行内部用线段树优化。这样点数是O(nm)的，边数是O(n^2m\log m)的，堆优化跑一个最短路时间复杂度就是O(n^2m\log m\log(n^2m\log m))。看起来很恐怖，但是经过实测边数不会超过20000000。（当然如果你足够强的话也可以写一个二维线段树）

下面贴出我的代码：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
struct Edge
{
    int to;
    int next;
    ll len;
}e[20000005];
ll n,m,edgenum,head[1000005],points;//points是线段树的节点数量
ll dis[1000005],a[305][305],b[305][305],ansx,ansy,ansz;
int lson[1000005],rson[1000005],root[305],p[305][305],x,y,z,xx,yy;//lson,rson是线段树的左右儿子的位置，root是每一行的线段树的跟的位置，p是每一个点对应的线段树的节点。
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
void add(int u,int v,ll l)
{
    e[++edgenum].len=l;
    e[edgenum].next=head[u];
    e[edgenum].to=v;
    head[u]=edgenum;
}
int build(int line,int o,int l,int r)在第line行，线段树节点编号是o，管辖的区间是[l,r]
{
    if(l==r)
    {
        p[line][l]=o;//在这里更新p，表示第line行第l列的点对应的节点是o
        return o;
    }
    int mid=l+r>>1;
    lson[o]=build(line,++points,l,mid);
    rson[o]=build(line,++points,mid+1,r);
    add(o,lson[o],0);//从父节点往孩子建边
    add(o,rson[o],0);
    return o;
}
void add2(int o,int l,int r,int node,int from,int to,ll v)//当前的线段树节点是o，管辖区间是[l,r]，要从node向[from,to]的区间连边权为v的边
{
//  printf("Enter:%d %d\n",l,r);
    if(l>=from&&r<=to)return add(node,o,v);
    int mid=l+r>>1;
    if(from<=mid)add2(lson[o],l,mid,node,from,to,v);
    if(to>mid)add2(rson[o],mid+1,r,node,from,to,v);
}
void Dijkstra(int u)//最短路板子
{
    for(int i=1;i<=points;i++)dis[i]=100000000000000000;
    dis[u]=0;
    q.push(make_pair(dis[u],u));
    while(!q.empty())
    {
        int node=q.top().second;
        ll len=q.top().first;
        q.pop();
        if(len!=dis[node])continue;
        for(int hd=head[node];hd;hd=e[hd].next)
        {
            int to=e[hd].to;
            if(dis[to]>dis[node]+e[hd].len)
            {
                dis[to]=dis[node]+e[hd].len;
                q.push(make_pair(dis[to],to));
            }
        }
    }
//  for(int i=1;i<=n;i++)
//  {
//      for(int j=1;j<=m;j++)
//        printf("%lld ",dis[p[i][j]]);
//      printf("\n");
//  }
//  printf("\n");
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)root[i]=build(i,++points,1,m);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%lld",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%lld",&b[i][j]);
//      printf("%d %d:\n",i,j);
        for(int k=max(1ll,i-a[i][j]);k<=min(n,i+a[i][j]);k++)
        {
            int rest=a[i][j]-abs(k-i);
//          printf("%d %d %d\n",k,max(1,j-rest),min(m,(ll)j+rest));
            add2(root[k],1,m,p[i][j],max(1,j-rest),min(m,(ll)j+rest),b[i][j]);
        }
    }
    scanf("%d%d",&xx,&yy);
    x=p[xx][yy];
    scanf("%d%d",&xx,&yy);
    y=p[xx][yy];
    scanf("%d%d",&xx,&yy);
    z=p[xx][yy];
//  for(int i=1;i<=points;i++)
//  {
//      printf("%d:",i);
//      for(int hd=head[i];hd;hd=e[hd].next)
//      {
//          printf("(%d %lld)",e[hd].to,e[hd].len);
//      }
//      printf("\n");
//  }
//  for(int i=1;i<=points;i++)
//  {
//      printf("%d:",i);
//      for(int hd=head[i];hd;hd=e[hd].next)
//      {
//          printf("(%d %lld)",e[hd].to,e[hd].len);
//      }
//      printf("\n");
//  }//看看这一堆一堆的注释，就知道我写题的时候有多么崩溃
    Dijkstra(x);
    ll xy=dis[y],xz=dis[z];
    Dijkstra(y);
    ll yx=dis[x],yz=dis[z];
    Dijkstra(z);
    ll zx=dis[x],zy=dis[y];
    ansx=yx+zx;
    ansy=xy+zy;
    ansz=xz+yz;
    if(ansx>100000000000000000&&ansy>100000000000000000&&ansz>100000000000000000)
    {
        printf("NO\n");
        return 0;
    }
    if(ansx<=ansy&&ansx<=ansz)printf("X\n%lld\n",ansx);
    else if(ansy<=ansx&&ansy<=ansz)printf("Y\n%lld\n",ansy);
    else printf("Z\n%lld\n",ansz);
    return 0;
}