专栏文章

题解：P3036 [USACO16DEC] Lasers and Mirrors G

AACcepted917
P3036题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miowo8ni
此快照首次捕获于
2025/12/03 02:22
3 个月前
此快照最后确认于
2025/12/03 02:22
3 个月前
查看原文

P3036 题解

题目传送门

分析

拆点法 + dijkstra

建图

将一个坐标点拆成四个点：
把一个“大”点拆成四个“小”点后，连接这些小点，使得任意两小点都有边，如图中红蓝色的双向边。其中，红色边代表光路要反射，需要一个镜子，所以边权为 11；蓝色边代表光路不用反射，直接穿过栅栏柱而不改变方向，不需要镜子，所以边权为 00。
将每个小点都编号，设大点的输入时的顺序排名为 idid，则每个小点对应的编号如上图所示，如最上方的小点编号为 4×(id−1)+2+1(=4×id+3−4)4 \times (id-1)+2+1(=4\times id+3-4)。
编号为 11 的小点设为激光器的位置，即起点；编号为 22 的小点设为谷仓的位置，即终点。
那么样例的图示为:
如图，绿色边不仅连接了小点，也连接了大点，如 44 号小点与 99 号小点的边，连接了 id=1id=1 和 22 的大点，表示光可以从 id=1id=1 的大点传递到 id=2id=2 的大点（反向也行，为双向边）。由于光沿直线传播，所以不需要反射镜，绿色边权为 00。
如何实现绿色边：
将大点以横坐标快速排序，找到横坐标相等的大点，把大点中合适的小点连接，如下图中的①②。
接着处理纵坐标，同理，排序后找纵坐标相等的大点，连接即可，如③④。
图中黑色边为起点、终点双向直达边，连接所有起点、终点与所有能直接通过传递光到达的大点，不需要反射镜，所以边权为 00，如下图①~④。
如何实现黑色边：
对于连接终点的黑色边，找到与其横、纵坐标相等的大点，连接大点中合适的小点，如下图①②。
对于连接起点的黑色边，同理连接即可，如图中③④。
红蓝色边同上。

最短路

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

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

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...