#B4208. [常州市程序设计小能手 2021] 移动

    ID: 8477 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>搜索图论2021江苏广度优先搜索 BFS小学科创活动

[常州市程序设计小能手 2021] 移动

题目背景

搬运自 http://czoj.com.cn/p/444。数据为民间数据。

题目描述

X\text X 学校的教学楼是一栋 HH 层的建筑。学生在同一楼层间可以自由移动,但是只有通过爬楼梯才可以上下楼层。
让我们把教学楼抽象成一个有 H×MH\times M 个格子的矩形,学生可以从一个单元格上花费 11 秒移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的(除了不能摔出楼外),但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续楼层,且一列中只会有一个楼梯对于这一部分叙述可以通过样例理解
现在有 TT 个学生,每个人都希望从一个位置走到另一个位置上。他们想问问小 X\text X 最短需要花费多长时间。

输入格式

第一行,22 个整数 HHMM 表示教学楼大小。
第二行,11 个整数 KK 表示楼梯的数量。
接下来 KK 行,每行三个整数 x,h1,h2x,h_1,h_2 表示在第 xx 列的 h1h_1 层和 h2h_2 层之间有楼梯。
接下来 11 行,一个整数 TT 表示有 TT 个学生。
接下来 TT 行,每行四个整数 sx,sy,tx,tys_x,s_y,t_x,t_y 表示这个学生想要从 sxs_x 列的 sys_y 层走到 txt_x 列的 tyty 层。

输出格式

对于每一个学生按顺序输出一行一个整数表示最短时间。
如果不可能走到,输出 -1

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

提示

样例解释

数据范围

对于所有数据,1xM1\le x\le M 且所有 xx 各不相同,$1\le h_1<h_2\le H,1\le s_x,t_x\le M,1\le s_y,t_y\le H,1\le H,M\le 10^5,1\le K\le 300,1\le T\le 5 \times 10^4$。