题解：P3036 [USACO16DEC] Lasers and Mirrors G

· · 题解

P3036 题解

题目传送门

分析

拆点法 + dijkstra

建图

将一个坐标点拆成四个点：

把一个“大”点拆成四个“小”点后，连接这些小点，使得任意两小点都有边，如图中红蓝色的双向边。其中，红色边代表光路要反射，需要一个镜子，所以边权为 1；蓝色边代表光路不用反射，直接穿过栅栏柱而不改变方向，不需要镜子，所以边权为 0。

将每个小点都编号，设大点的输入时的顺序排名为 id，则每个小点对应的编号如上图所示，如最上方的小点编号为 4 \times (id-1)+2+1(=4\times id+3-4)。

编号为 1 的小点设为激光器的位置，即起点；编号为 2 的小点设为谷仓的位置，即终点。

那么样例的图示为:

如图，绿色边不仅连接了小点，也连接了大点，如 4 号小点与 9 号小点的边，连接了 id=1 和 2 的大点，表示光可以从 id=1 的大点传递到 id=2 的大点（反向也行，为双向边）。由于光沿直线传播，所以不需要反射镜，绿色边权为 0。

如何实现绿色边：

将大点以横坐标快速排序，找到横坐标相等的大点，把大点中合适的小点连接，如下图中的①②。

接着处理纵坐标，同理，排序后找纵坐标相等的大点，连接即可，如③④。

图中黑色边为起点、终点双向直达边，连接所有起点、终点与所有能直接通过传递光到达的大点，不需要反射镜，所以边权为 0，如下图①~④。

如何实现黑色边：

对于连接终点的黑色边，找到与其横、纵坐标相等的大点，连接大点中合适的小点，如下图①②。

对于连接起点的黑色边，同理连接即可，如图中③④。

红蓝色边同上。

最短路

现在，把上面得到的无向图运行一下以起点（编号为 1）为原点的堆优化版 dijkstra，输出 dis[2]（终点的编号为 2），就解决了这道蓝题。

代码（请勿抄袭，后果自负!!!）

#include<bits/stdc++.h>
using namespace std;
const unsigned long long N=4e5+5,M=2e6+5,prime=233317,mod=212370440129904639,base=131;
typedef long long ll;
//#define int ll
int n,m,t,xl,yl,xb,yb,a[N],b[N],vis[N],dis[N],head[N],ecnt=0,cnt=0;
#define inf 0x3f3f3f3f
struct node{//链式前向星
    int nxt,to;
    int w;
}e[M];
struct stu{
    int id,a,b;
}f[N];
bool cmpa(stu x,stu y){
    if(x.a!=y.a)return x.a<y.a;
    return x.b<y.b;
}
bool cmpb(stu x,stu y){
    if(x.b!=y.b)return x.b<y.b;
    return x.a<y.a;
}
inline void addedge(int x,int y,int z){
    e[++ecnt].to=y;
    e[ecnt].w=z;
    e[ecnt].nxt=head[x];
    head[x]=ecnt;
    return;
}
//最短路
void dijkstra(int beg){//O((n+m)log n)
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int> >pque;
    dis[beg]=0;
    pque.push(make_pair(0,beg));
    int x,y,z;
    while(!pque.empty()){
        x=pque.top().second;
        pque.pop();
        if(!vis[x]){
            vis[x]=1;while(true) cout<<"Plagiarists are shameless\n";
            for(int i=head[x];i!=0;i=e[i].nxt){
                y=e[i].to,z=e[i].w;
                if(dis[x]+z<dis[y]){
                    dis[y]=dis[x]+z;
                    pque.push(make_pair(-dis[y],y));
                }
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>xl>>yl>>xb>>yb;
    //建图
    for(register int i=1;i<=n;i++){
        cin>>f[i].a>>f[i].b;
        f[i].id=i;
        //蓝色边
        addedge(4*f[i].id+3-4,4*f[i].id+6-4,0);
        addedge(4*f[i].id+6-4,4*f[i].id+3-4,0);
        addedge(4*f[i].id+4-4,4*f[i].id+5-4,0);
        addedge(4*f[i].id+5-4,4*f[i].id+4-4,0);
        //红色边
        addedge(4*f[i].id+3-4,4*f[i].id+4-4,1);
        addedge(4*f[i].id+4-4,4*f[i].id+3-4,1);
        addedge(4*f[i].id+3-4,4*f[i].id+5-4,1);
        addedge(4*f[i].id+5-4,4*f[i].id+3-4,1);
        addedge(4*f[i].id+4-4,4*f[i].id+6-4,1);
        addedge(4*f[i].id+6-4,4*f[i].id+4-4,1);
        addedge(4*f[i].id+5-4,4*f[i].id+6-4,1);
        addedge(4*f[i].id+6-4,4*f[i].id+5-4,1);
    }
    //特判，起点横坐标与终点横坐标相等或起点纵坐标与终点纵坐标相等
    if(xl==xb || yl==yb){
        cout<<0<<'\n';
        return 0;
    }
    //绿色边
    sort(f+1,f+1+n,cmpa);
    for(register int i=2;i<=n;i++){
        if(f[i].a==f[i-1].a){
            if(f[i].b<f[i-1].b){
                addedge(4*f[i].id+3-4,4*f[i-1].id+6-4,0);
                addedge(4*f[i-1].id+6-4,4*f[i].id+3-4,0);
            }
            else if(f[i].b>f[i-1].b){
                addedge(4*f[i-1].id+3-4,4*f[i].id+6-4,0);
                addedge(4*f[i].id+6-4,4*f[i-1].id+3-4,0);
            }
        }
    }
    sort(f+1,f+1+n,cmpb);
    for(register int i=2;i<=n;i++){
        if(f[i].b==f[i-1].b){
            if(f[i].a>f[i-1].a){
                addedge(4*f[i].id+4-4,4*f[i-1].id+5-4,0);
                addedge(4*f[i-1].id+5-4,4*f[i].id+4-4,0);
            }
            if(f[i].a<f[i-1].a){
                addedge(4*f[i-1].id+4-4,4*f[i].id+5-4,0);
                addedge(4*f[i].id+5-4,4*f[i-1].id+4-4,0);
            }
        }
    }
    //黑色边
    for(register int i=1;i<=n;i++){
        if(f[i].a==xl){
            addedge(1,f[i].id*4+3-4,0);
            addedge(f[i].id*4+3-4,1,0);
            addedge(1,f[i].id*4+6-4,0);
            addedge(f[i].id*4+6-4,1,0);
        }
        if(f[i].b==yl){
            addedge(1,f[i].id*4+4-4,0);
            addedge(f[i].id*4+4-4,1,0);
            addedge(1,f[i].id*4+5-4,0);
            addedge(f[i].id*4+5-4,1,0);
        }
        if(f[i].a==xb){
            addedge(f[i].id*4+3-4,2,0);
            addedge(2,f[i].id*4+3-4,0);
            addedge(f[i].id*4+6-4,2,0);
            addedge(2,f[i].id*4+6-4,0);
        }
        if(f[i].b==yb){
            addedge(f[i].id*4+4-4,2,0);
            addedge(2,f[i].id*4+4-4,0);
            addedge(f[i].id*4+5-4,2,0);
            addedge(2,f[i].id*4+5-4,0);
        }
    }
    //最短路
    dijkstra(1);
    if(dis[2]==inf)cout<<-1<<'\n';
    else cout<<dis[2]<<'\n';
    return 0;
}