#P3161. 孤舟蓑笠翁
孤舟蓑笠翁
孤舟蓑笠翁
题目背景
为了保护洞庭湖的鱼类,只有选拔中最优秀的渔翁才能继续捕鱼。如今湖上只剩蓑笠翁一人,不能再像从前那样和其他渔翁一起钓鱼、打牌、切磋武艺。闲暇时,他便练起相传由周伯通首创的左右互搏术。
题目描述
练功时,蓑笠翁的双手在同一竖直平面内运动。取该平面上一点作为原点,以向右和向上分别为 轴、 轴的正方向。平面上有 个可停顿点,第 个点的坐标是 。
每一秒,两只手都处于各自的可停顿点上。若左手在 号点、右手在 号点,则必须满足
每秒末,两只手可以同时移动。每只手可以保持不动,或者按照属于该手的一条移动条件,从当前点移到另一个点。每条条件所连的两点可以双向移动。移动后,两只手所在点的曼哈顿距离仍须满足上述限制。
左右互搏术共有 种绝招。左手在 号点、右手在 号点时,可以发动第 种绝招。对每种绝招 ,求从它的姿势出发,经过合法移动到达其他任意一种绝招姿势的最少秒数。
输入格式
第一行有两个正整数 ,表示停顿点数和移动条件数。
第二行有两个非负整数 ,表示允许的距离区间。
接下来 行,第 行有两个正整数 ,表示 号停顿点的坐标。
接下来一行是一个正整数 ,再接下来 行,第 行给出 ,分别表示第 种绝招需要的左手和右手的停顿点。各绝招姿势互不相同,并且都满足距离限制。
最后 行,每行有三个整数 。 表示左手可以在 之间移动, 表示右手可以在 之间移动。所有停顿点编号均为 至 。
输出格式
输出 行。第 行给出发动第 种绝招后,到达一种不同绝招所需的最少秒数。如果无法到达其他绝招,输出 。
样例
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
从第 种绝招出发,先同时把左手移到 号点、右手移到 号点,再把左手移到 号点,右手保持不动。这样用两秒到达第 种绝招。倒过来即可从第 种绝招到达第 种。发出第 种绝招时,右手所在的 号点没有可走的右手移动条件,因此不能到达另两种绝招。
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
数据范围
- 其中 的数据,、、。
- 另有 的数据,、、、、。
- 对于全部数据,、、、。