题解 P3632 【[APIO2011]寻路】

· · 题解

每个矩形能够生成的节点个数最多为12个 因此点数是O(n)级别的

每个点仅需与其相邻的节点连边（至多4个）

因此边数也是O(n)级别的

复杂度O(n^2)

期望得分：100

#include <queue>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#define vd void
#define il inline

#define re register
#define INF 20000000000000LL
#define mp(x,y) make_pair((x),(y))
#define FOR(i,a,b) for(re int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(re int i=(a);i>=(b);--i)

#define gc pad==pb&&(pb=(pad=buf)+fread(buf,1,1<<17,stdin),pad==pb)?EOF:*pad++

using namespace std;

static char buf[1<<17],*pad(buf),*pb(buf);

const int N(1007);

typedef long long ll;
typedef pair<ll,int> pa;
priority_queue <pa,vector<pa>,greater<pa> > q;

ll d[N*100];
int T,n,cnt,lcnt,cn;
int head[N*100],vis[N*100];

il int abs(int x) {
    return x>0?x:-x;
}

struct Node {
    int l,r,x;
    vector<int> s;
    Node() {}
    Node(int l,int r,int x):l(l),r(r),x(x) {s.clear();}
    bool operator < (const Node &f) const {
        return x<f.x;
    }
}r[N*5+5],c[N*5+5];

struct node {
    int x,y;
    node() {}
    node(int x,int y):x(x),y(y){}
    friend int dis(node x,node y){return abs(x.x-y.x)+abs(x.y-y.y);}
    bool operator == (const node&b) const{
        return x==b.x&&y==b.y;
    }
}pan[N*100];

struct Edge {
    int next,to,wi;
}edge[N*100];

il int read() {
    re int s=0,f=1;re char ch(gc);
    while(ch<'0'||ch>'9') ch=='-'?f=-1,ch=gc:ch=gc;
    while(ch<='9'&&ch>='0') s=s*10+ch-48,ch=gc;
    return f*s;
}

il bool cmp(int x,int y) {
    return pan[x].x==pan[y].x?pan[x].y<pan[y].y:pan[x].x<pan[y].x;
}

il vd add(int x,int y,int w) {
    edge[++cn]=(Edge){head[x],y,w};head[x]=cn;
}

vd dijkstra() {
    memset(d,127,sizeof(d)),memset(vis,false,sizeof(vis));
    q.push(mp(d[1]=0,1));
    while(!q.empty()) {
        int now(q.top().second);q.pop();
        if(vis[now]) continue;
        vis[now]=true;
        for(re int i=head[now];i;i=edge[i].next) {
            int v(edge[i].to);
            if(d[v]>d[now]+edge[i].wi) {
                d[v]=d[now]+edge[i].wi;
                q.push(mp(d[v],v));
            }
        }
    }
}

vd Main() {
    T=read();
    while(T--) {
        cnt=lcnt=cn=0;
        memset(head,0,sizeof(head));
        int fx(read()),fy(read()),tx(read()),ty(read());
        pan[++cnt]=node(fx,fy);pan[++cnt]=node(tx,ty);    
        if(fx==tx||fy==ty) add(1,2,dis(pan[1],pan[2])),add(2,1,dis(pan[1],pan[2]));
        n=read();
        FOR(i,1,n) {
            int x1(read()),y1(read()),x2(read()),y2(read());
            if(x1>x2) swap(x1,x2);if(y1>y2) swap(y1,y2);
            pan[++cnt]=node(x1,y1),pan[++cnt]=node(x1,y2);
            pan[++cnt]=node(x2,y1),pan[++cnt]=node(x2,y2);
            c[++lcnt]=Node(cnt-3,cnt-1,y1),r[lcnt]=Node(cnt-3,cnt-2,x1);
            c[++lcnt]=Node(cnt-2,cnt,y2),r[lcnt]=Node(cnt-1,cnt,x2);
        }
        sort(c+1,c+lcnt+1),sort(r+1,r+lcnt+1);
        for(int i=cnt;i;--i) {
            int j,id;node now;
            j=lower_bound(c+1,c+lcnt+1,Node(0,0,pan[i].y))-c-1;
            for(;j&&!(pan[c[j].l].x<=pan[i].x&&pan[c[j].r].x>=pan[i].x);--j);
            if(j) {
                 now=node(pan[i].x,c[j].x);
                if(now==pan[c[j].l]) id=c[j].l;
                else if(now==pan[c[j].r]) id=c[j].r;
                else pan[id=++cnt]=now;
                add(i,id,dis(now,pan[i]));
                add(id,i,dis(now,pan[i]));
                c[j].s.push_back(id);
            }
            j=upper_bound(c+1,c+lcnt+1,Node(0,0,pan[i].y))-c;
            for(;j<=lcnt&&!(pan[c[j].l].x<=pan[i].x&&pan[c[j].r].x>=pan[i].x);++j);
            if(j<=lcnt) {
                now=node(pan[i].x,c[j].x);
                if(now==pan[c[j].l]) id=c[j].l;
                else if(now==pan[c[j].r]) id=c[j].r;
                else pan[id=++cnt]=now;
                add(i,id,dis(now,pan[i]));
                add(id,i,dis(now,pan[i]));
                c[j].s.push_back(id);
            }
            j=lower_bound(r+1,r+lcnt+1,Node(0,0,pan[i].x))-r-1;
            for(;j&&!(pan[r[j].l].y<=pan[i].y&&pan[r[j].r].y>=pan[i].y);--j);
            if(j<=lcnt) {
                now=node(r[j].x,pan[i].y);
                if(now==pan[r[j].l]) id=r[j].l;
                else if(now==pan[r[j].r]) id=r[j].r;
                else pan[id=++cnt]=now;
                add(i,id,dis(now,pan[i]));
                add(id,i,dis(now,pan[i]));
                r[j].s.push_back(id);
            }
            j=upper_bound(r+1,r+lcnt+1,Node(0,0,pan[i].x))-r;
            for(;j<=lcnt&&!(pan[r[j].l].y<=pan[i].y&&pan[r[j].r].y>=pan[i].y);++j);
            if(j<=lcnt) {
                now=node(r[j].x,pan[i].y);
                if(now==pan[r[j].l]) id=r[j].l;
                else if(now==pan[r[j].r]) id=r[j].r;
                else pan[id=++cnt]=now;
                add(i,id,dis(now,pan[i]));
                add(id,i,dis(now,pan[i]));
                r[j].s.push_back(id);
            }
        }
        FOR(i,1,lcnt) {
            sort(c[i].s.begin(),c[i].s.end(),cmp);
            FOR(j,1,c[i].s.size()-1){
                add(c[i].s[j],c[i].s[j-1],dis(pan[c[i].s[j]],pan[c[i].s[j-1]]));
                add(c[i].s[j-1],c[i].s[j],dis(pan[c[i].s[j]],pan[c[i].s[j-1]]));
            }
            sort(r[i].s.begin(),r[i].s.end(),cmp);
            FOR(j,1,r[i].s.size()-1) {
                add(r[i].s[j],r[i].s[j-1],dis(pan[r[i].s[j]],pan[r[i].s[j-1]]));
                add(r[i].s[j-1],r[i].s[j],dis(pan[r[i].s[j]],pan[r[i].s[j-1]]));
            }
        }
        dijkstra();
        if(d[2]<INF) 
            printf("%lld\n",d[2]);
        else 
            puts("No Path");
    }
}

int main() {
    Main();
    return (0);
}

/*
2
1 7 7 8
2
2 5 3 8
4 10 6 7
2 1 5 4
1
3 1 4 3
*/