题解：P7702 [CCC 2014] 登机口

jch123 · 2026-11-10 17:10:45 · 题解

题意

有一些登机口，登机口之间都是一百米，有一些扶梯连接一对登机口（扶梯之间速度不同），还有一个走路的速度，对此查询从一个登机口走到另外一个登机口的最短路，保证同一方向的扶梯不交。

思路

只保留有扶梯连接的点，设这些关键点为 p。如果想跨过 [k,k+1]，那么跨过的那一刻必然到达 p_k,p_{k+1} 与跨过 [k,k+1] 的两条扶梯的终点这四个点中的一个。

处理 D_{k,i,j} 代表 k 的四点中 i\to j 的最短路，可以通过扫一遍前缀/后缀来完成（正确性通过没有方向相同且重叠的区间保证）。然后可以大力线段树维护矩阵转移，对于询问，只需要让询问的点走到左/右第一个关键点即可，然后线段树把中间的转移算上，再考虑最后一段。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,M=1e12;
int a[N],b[N],A[N],B[N],S[N],p[N],nl[N],nr[N],pl[N],pr[N],v[N][4];
double D[N][4][4],dis[N],ndis[N];
int n,m,q,W,G,K;
void floyd(int p)
{
    for(int k=0;k<4;k++)
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    D[p][i][j]=min(D[p][i][j],D[p][i][k]+D[p][k][j]);
}
struct mat
{
    double c[4][4];
}tl[4*N],tr[4*N];
mat mul(mat &x,mat &y)
{
    mat z;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            double res=M;
            for(int k=0;k<4;k++) res=min(res,x.c[i][k]+y.c[k][j]);
            z.c[i][j]=res;
        }
    return z;
}
void upd(mat &x)
{
    for(int i=0;i<4;i++)
        ndis[i]=M;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            ndis[j]=min(ndis[j],dis[i]+x.c[i][j]);
    for(int i=0;i<4;i++)
        dis[i]=ndis[i];
}
void push_up(int p){tl[p]=mul(tl[p*2+1],tl[p*2]),tr[p]=mul(tr[p*2],tr[p*2+1]);}
void build(int p,int l,int r)
{
    if(l==r)
    {
        for(int a=0;a<4;a++)
            for(int b=0;b<4;b++)
                tl[p].c[a][b]=tr[p].c[a][b]=M;
        for(int x=0;x<4;x++)
            for(int y=0;y<4;y++)
                if(v[l][x]==v[l+1][y])
                    for(int a=0;a<4;a++)
                        for(int b=0;b<4;b++)
                            tl[p].c[a][b]=min(tl[p].c[a][b],D[l+1][a][y]+D[l][x][b]),tr[p].c[a][b]=min(tr[p].c[a][b],D[l][a][x]+D[l+1][y][b]);
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
    push_up(p);
}
void asl(int p,int l,int r,int s,int t)
{
    if(l>=s&&r<=t)
    {
        upd(tl[p]);
        return;
    }
    int mid=(l+r)>>1;
    if(mid<t) asl(p*2+1,mid+1,r,s,t);
    if(s<=mid) asl(p*2,l,mid,s,t);
}
void asr(int p,int l,int r,int s,int t)
{
    if(l>=s&&r<=t)
    {
        upd(tr[p]);
        return;
    }
    int mid=(l+r)>>1;
    if(s<=mid) asr(p*2,l,mid,s,t);
    if(mid<t) asr(p*2+1,mid+1,r,s,t);
}
int fd(int x)
{
    int t=upper_bound(p+1,p+1+m,x)-p-1;
    if(t<1) t=1;
    if(t>K) t=K;
    return t;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>G>>W>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>A[i]>>B[i]>>S[i],p[++m]=A[i],p[++m]=B[i];
    sort(p+1,p+1+m);
    m=unique(p+1,p+1+m)-(p+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(p+1,p+1+m,A[i])-p,b[i]=lower_bound(p+1,p+1+m,B[i])-p;
        int x=a[i],y=b[i];
        if(x<y) nr[x]=y,pr[x]=p[y];
        else nl[y]=x,pl[y]=p[y];
    }
    K=m-1;
    int tl=0,tr=0,ml=0,mr=0;
    for(int k=1;k<=K;k++)
    {
        if(nr[k]>mr) mr=nr[k],tr=pr[k];
        if(nl[k]>ml) ml=nl[k],tl=pl[k];
        v[k][0]=p[k],v[k][1]=p[k+1],v[k][2]=(mr>k?tr:p[k+1]),v[k][3]=(ml>k?tl:p[k]);
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                D[k][i][j]=(v[k][i]==v[k][j]?0:1e12);   
        double t=100.0*(p[k+1]-p[k])/W;
        D[k][0][1]=min(D[k][0][1],t),D[k][1][0]=min(D[k][1][0],t);        
    }
    for(int i=1;i<=n;i++)
    {
        int x=a[i],y=b[i];
        double t=100.0*fabs(A[i]-B[i])/(W+S[i]);
        if(x<y) D[x][0][2]=min(D[x][0][2],t);
        else D[x-1][1][3]=min(D[x-1][1][3],t);
    }
    floyd(1);
    for(int k=2;k<=K;k++)
    {
        for(int a=0;a<4;a++)
            for(int c=0;c<4;c++)
                if(v[k-1][a]==v[k][c])
                    for(int b=0;b<4;b++)
                        for(int d=0;d<4;d++)
                            if(v[k-1][b]==v[k][d])
                                D[k][c][d]=min(D[k][c][d],D[k-1][a][b]);
        floyd(k);
    }
    for(int k=K-1;k>=1;k--)
    {
        for(int a=0;a<4;a++)
            for(int c=0;c<4;c++)
                if(v[k+1][a]==v[k][c])
                    for(int b=0;b<4;b++)
                        for(int d=0;d<4;d++)
                            if(v[k+1][b]==v[k][d])
                                D[k][c][d]=min(D[k][c][d],D[k+1][a][b]);
        floyd(k);
    }
    if(K>=2) build(1,1,K-1);
    cout<<fixed<<setprecision(14);
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        double ans=100.0*fabs(x-y)/W;
        int kx=fd(x),ky=fd(y);
        for(int i=0;i<4;i++)
            dis[i]=min(100.0*abs(x-v[kx][0])/W+D[kx][0][i],100.0*abs(x-v[kx][1])/W+D[kx][1][i]);
        if(kx<ky) asr(1,1,K-1,kx,ky-1);
        else if(kx>ky) asl(1,1,K-1,ky,kx-1);
        ans=min({ans,dis[0]+100.0*abs(v[ky][0]-y)/W,dis[1]+100.0*abs(v[ky][1]-y)/W});
        cout<<ans<<'\n';
    }
    return 0;
}