Mystia 的居酒屋 题解

TinyKiecoo · 2023-09-12 13:18:33 · 个人记录

• (i,j)$ 到 $(p,k_2)

其中 k_1<k_2 且 i≠p。

经过观察，我们没有必要连 (p,k_2) 的边，只连 (i,j) 到 (p,k_1) 的边就好。也就是说 (i,j) 向 (p,k) 连边，只连 k 最小的那一条。我们可以二分找出连哪一条。

这样还不够，我们必须额外加上一类边以弥补少连的那部分：即从 (i,j) 到 (i,j+1) 连权值为 C_{j+1}-C_j 的边。可以简单地理解为允许我们在过桥的时候实现“换盘”的操作。

这样之前省掉的从 (i,j) 到 (p,k_2) 的边就可以由从 (i,j) 到 (p,k_1) 的边，加上一系列从 (p,k_3) 到 (p,k_3+1) 的边替代了。

预处理加边的复杂度 \rm O(\it N^{\rm2}M)，点数还是 \rm O(\it NM)，边数 \rm O(\it N^{\rm2}M)。

最后跑最短路，总复杂度为 \rm O(\it N^{\rm2}M \log{(N^{\rm2}M)})，本题开启 O2 优化且时限为两秒，期望得分 100 分。

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int T,n,m,tpm,w,t,tp,x[101],y[101],d[20102],head[20102],dis[20102],cnt,toNumCnt;
bool f[20102];
map<pair<int,int>,int>M;
struct node {
    int to,val,nxt;
} e[1000001];
inline int read(){
    int o=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        o=o*10+ch-'0';
        ch=getchar();
    }
    return o;
}
struct Node {
    int r,c;
    bool invalid;
} p[20102];
inline bool cmp(Node xx,Node yy) {
    if(xx.invalid!=yy.invalid)return xx.invalid<yy.invalid;
    return xx.r<yy.r;
}
int binarySearch(int l,int r,double target) {
    if(l>r)return 0;
    if(l==r) {
        if(p[l].r>=target)return l;
        else return 0;
    }
    int mid=((l+r)>>1);
    if(p[mid].r==target)return mid;
    if(p[mid].r>target)return binarySearch(l,mid,target);
    return binarySearch(mid+1,r,target);
}
inline int toNum(int i,int j) {
    pair<int,int>pp=make_pair(i,j);
    if(M.find(pp)==M.end()) {
        M.insert(make_pair(pp,++toNumCnt));
        return toNumCnt;
    }
    return M[pp];
}
inline double ddis(long long X,long long Y,long long xx,long long yy) {
    return sqrt((X-xx)*(X-xx)+(Y-yy)*(Y-yy));
}
inline void add(int xx,int yy,int zz) {
    e[++cnt].to=yy;
    e[cnt].val=zz;
    e[cnt].nxt=head[xx];
    head[xx]=cnt;
}
int main() {
    T=read();
    while(T--) {
        memset(f,0,sizeof(f));
        cnt=0;
        toNumCnt=1;
        M.clear();
        memset(head,0,sizeof(head));
        memset(p,0,sizeof(p));
        n=read();
        m=read();
        w=read();
        tpm=m;
        for(int i=1; i<=n; i++){
            x[i]=read();
            y[i]=read();
        }
        for(int i=1; i<=m; i++){
            p[i].r=read();
            p[i].c=read();
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=m; j++) {
                if(p[i].r<=p[j].r&&p[i].c>=p[j].c&&i!=j&&!p[j].invalid) {
                    p[i].invalid=true;
                    tpm--;
                    break;
                }
            }
        }
        sort(p,p+m+1,cmp);
        m=tpm;
        for(int i=1; i<=n; i++) {
            tp=binarySearch(1,m,y[i]);
            if(tp)add(0,toNum(i,tp),p[tp].c);
            tp=binarySearch(1,m,w-y[i]);
            if(tp)for(int j=tp;j<=m;j++)add(toNum(i,j),1,0);
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(j!=m)add(toNum(i,j),toNum(i,j+1),p[j+1].c-p[j].c);
                for(int ii=1; ii<=n; ii++) {
                    if(ii==i)continue;
                    tp=binarySearch(1,m,ddis(x[i],y[i],x[ii],y[ii])-p[j].r);
                    if(tp)add(toNum(i,j),toNum(ii,tp),p[tp].c);
                }
            }
        }
        memset(d,0x3f,sizeof(d));
        d[0]=0;
        q.push(make_pair(0,0));
        while(!q.empty()) {
            t=q.top().second;
            q.pop();
            if(f[t])continue;
            f[t]=1;
            for(int i=head[t]; i; i=e[i].nxt) {
                if(d[t]+e[i].val<d[e[i].to]) {
                    d[e[i].to]=d[t]+e[i].val;
                    q.push(make_pair(d[e[i].to],e[i].to));
                }
            }
        }
        if(d[1]>1e9)puts("impossib1e");
        else printf("%d\n",d[1]);
    }
}