题解 P5471 【[NOI2019]弹跳】

· · 题解

处理这类特殊连边的套路方法(边权非负):

以下边的含义都是特殊边，形如从集合 S_1 中的所有点连向集合 S_2 中的所有点.

直接使用某种数据结构连边之后跑 dijkstra，复杂度 O((n+\text{边数})\times \log (n+\text{边数})).(实际上使用斐波那契堆可以做到O(\text{边数}+n\log n)，但为了方便还是使用 stl 的优先队列来完成).一般来说边数就是 m\times \text{数据结构单次复杂度}.

然而可以把到边和点的最短路一起用 dijkstra 维护.具体地，定义到一条边的最短路为其所有起点的最短路的最小值加上边长，每次从堆中取出长度最短的元素，如果该元素为点那么就更新所有起点包含它的边的最短路，否则的话就更新该边的所有终点的最短路.那么由于每次堆中取出的都是最短路，所以每个元素都只会被更新一次.事实上我们通常写的 dijkstra 是省略了边的做法.

那么看一下我们需要做什么:取出所有起点包含某个点的边，取出某条边的所有终点，删除一条边或一个点.找一个数据结构维护即可.这样复杂度是 O((n+m)\times \text{数据结构单次复杂度}+(n+m)\log).一般点和边的操作可能不是通过一个数据结构来完成的，但为了方便姑且这样写.

具体到这道题，发现找边的操作可以直接用 vector 进行，找/删点的操作可以使用树套树或者 kdtree 完成，删边没有必要因为起点总在边之前删掉.边和点的松弛可以放在一起进行.

以下是常数巨大的线段树套 set 的代码.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int N=300005;
struct Edge{int w,x1,x2,y1,y2;}tmpe[N];
vector<int>e[N];
struct Point{int x,y;}pos[N];
struct Node{int id,dis;bool operator <(const Node &a)const{return dis>a.dis;}};
set<pair<int,int> >a[N];
priority_queue<Node>q;
int dis[N],n,m,tmp[N],vis[N],W,H;
void ins(int rot,int lt,int rt,int x,pair<int,int>w)
{
    a[rot].insert(w);
    if(lt==rt)return;
    int mid=(lt+rt)>>1;
    if(x<=mid)ins(rot<<1,lt,mid,x,w);
    else ins(rot<<1|1,mid+1,rt,x,w);
}
void del(int rot,int lt,int rt,int x,pair<int,int>w)
{
    a[rot].erase(w);
    if(lt==rt)return;
    int mid=(lt+rt)>>1;
    if(x<=mid)del(rot<<1,lt,mid,x,w);
    else del(rot<<1|1,mid+1,rt,x,w);
}
void update(int rot,int lt,int rt,int x1,int x2,int y1,int y2,int w)
{
    if(lt>=x1&&rt<=x2)
    {
        if(!a[rot].size())return;
        set<pair<int,int> >::iterator L=a[rot].lower_bound(make_pair(y1,0)),R=a[rot].upper_bound(make_pair(y2,114514));
        int tn=0;
        for(set<pair<int,int> >::iterator i=L;i!=R;i++)
        {
            int u=i->second;dis[u]=w;tmp[++tn]=u;
            for(vector<int>::iterator it=e[u].begin();it!=e[u].end();it++)
                q.push((Node){*it,tmpe[*it].w+w});
        }
        for(int i=1;i<=tn;i++)del(1,1,W,pos[tmp[i]].x,make_pair(pos[tmp[i]].y,tmp[i]));
        return;
    }
    int mid=(lt+rt)>>1;
    if(x1<=mid)update(rot<<1,lt,mid,x1,x2,y1,y2,w);
    if(x2>mid)update(rot<<1|1,mid+1,rt,x1,x2,y1,y2,w);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&W,&H);
    for(int i=1,x,y;i<=n;i++)scanf("%d%d",&pos[i].x,&pos[i].y),ins(1,1,W,pos[i].x,make_pair(pos[i].y,i));
    for(int i=1,x,t,L,R,D,U;i<=m;i++)
    {
        scanf("%d%d%d%d%d%d",&x,&t,&L,&R,&D,&U);
        e[x].push_back(i);tmpe[i]=(Edge){t,L,R,D,U};
    }
    dis[1]=0;for(int i=2;i<=n;i++)dis[i]=1e9;
    for(vector<int>::iterator it=e[1].begin();it!=e[1].end();it++)q.push((Node){*it,tmpe[*it].w});
    while(!q.empty())
    {
        Node t=q.top();q.pop();
        if(vis[t.id])continue;vis[t.id]=1;
        update(1,1,W,tmpe[t.id].x1,tmpe[t.id].x2,tmpe[t.id].y1,tmpe[t.id].y2,t.dis);
    }
    for(int i=2;i<=n;i++)printf("%d\n",dis[i]);
}