#P3161. 孤舟蓑笠翁

    ID: 2337 传统题 1000ms 512MiB 尝试: 88 已通过: 41 难度: 6 上传者: 标签>难度分类提高图论状态扩展图枚举与搜索多源 BFS状态编码CF21002013湖北互测week1

孤舟蓑笠翁

孤舟蓑笠翁

题目背景

为了保护洞庭湖的鱼类,只有选拔中最优秀的渔翁才能继续捕鱼。如今湖上只剩蓑笠翁一人,不能再像从前那样和其他渔翁一起钓鱼、打牌、切磋武艺。闲暇时,他便练起相传由周伯通首创的左右互搏术。

题目描述

练功时,蓑笠翁的双手在同一竖直平面内运动。取该平面上一点作为原点,以向右和向上分别为 xx 轴、yy 轴的正方向。平面上有 nn 个可停顿点,第 ii 个点的坐标是 (xi,yi)(x_i,y_i)。

每一秒,两只手都处于各自的可停顿点上。若左手在 ll 号点、右手在 rr 号点,则必须满足

dmin⁡≤∣xl−xr∣+∣yl−yr∣≤dmax⁡.d_{\min}\le |x_l-x_r|+|y_l-y_r|\le d_{\max}.

每秒末,两只手可以同时移动。每只手可以保持不动,或者按照属于该手的一条移动条件,从当前点移到另一个点。每条条件所连的两点可以双向移动。移动后,两只手所在点的曼哈顿距离仍须满足上述限制。

左右互搏术共有 kk 种绝招。左手在 viv_i 号点、右手在 uiu_i 号点时,可以发动第 ii 种绝招。对每种绝招 ii,求从它的姿势出发,经过合法移动到达其他任意一种绝招姿势的最少秒数。

输入格式

第一行有两个正整数 n,mn,m,表示停顿点数和移动条件数。

第二行有两个非负整数 dmin⁡,dmax⁡d_{\min},d_{\max},表示允许的距离区间。

接下来 nn 行,第 ii 行有两个正整数 xi,yix_i,y_i,表示 ii 号停顿点的坐标。

接下来一行是一个正整数 kk,再接下来 kk 行,第 ii 行给出 vi,uiv_i,u_i,分别表示第 ii 种绝招需要的左手和右手的停顿点。各绝招姿势互不相同,并且都满足距离限制。

最后 mm 行,每行有三个整数 a,b,typea,b,\mathrm{type}。type=0\mathrm{type}=0 表示左手可以在 a,ba,b 之间移动,type=1\mathrm{type}=1 表示右手可以在 a,ba,b 之间移动。所有停顿点编号均为 11 至 nn。

输出格式

输出 kk 行。第 ii 行给出发动第 ii 种绝招后,到达一种不同绝招所需的最少秒数。如果无法到达其他绝招,输出 −1-1。

样例

5 5
1 6
3 2
9 2
7 3
7 8
4 9
3
5 4
1 3
1 2
1 2 0
2 5 0
1 5 1
1 3 1
3 4 1
2
2
-1

从第 11 种绝招出发,先同时把左手移到 22 号点、右手移到 33 号点,再把左手移到 11 号点,右手保持不动。这样用两秒到达第 22 种绝招。倒过来即可从第 22 种绝招到达第 11 种。发出第 33 种绝招时,右手所在的 22 号点没有可走的右手移动条件,因此不能到达另两种绝招。

6 14
2 7
3 10
8 9
3 4
6 5
3 10
6 7
4
6 2
1 2
5 2
3 6
5 2 0
4 5 1
2 3 1
5 4 0
1 2 1
1 4 0
6 4 1
5 4 1
4 6 0
1 5 0
4 1 0
6 4 0
5 5 0
1 2 0
2
1
1
-1

数据范围

  • 其中 20%20\% 的数据,n≤50n\le 50、m≤100m\le 100、k≤100k\le 100。
  • 另有 30%30\% 的数据,n≤500n\le 500、m≤2000m\le 2000、k≤104k\le 10^4、dmin⁡=0d_{\min}=0、dmax⁡=104d_{\max}=10^4。
  • 对于全部数据,n≤1000n\le 1000、m≤4000m\le 4000、1≤xi,yi≤10001\le x_i,y_i\le 1000、0≤dmin⁡≤dmax⁡≤1090\le d_{\min}\le d_{\max}\le 10^9。