星星星 25 6月笔试题

岗位android系统优化

在宇宙之中存在虫洞，宇宙飞船在虫洞中航行时经历的时间流速比一般空间更慢，因此进入虫洞可以进行快速的旅行。现在在一个二维空间中，你需要设计一个程序，能够计算出在当前空间内的某一坐标点旅行至另一坐标点所需的时间。宇宙飞船只能在水平与垂直方向上运动，且在一般空间内，每单位距离移动需要1单位时间。

一般而言，若不考虑虫洞，从点(x_1,y_1)移动至点(x_2,y_2)所需的时间为

TIME=|x_2-x_1|+|y_2-y_1|

输入：
1. 一行一个整数，表示总共需要检测多少个情况
2. 一行一个整数，表示这一个情况中需要考虑多少个虫洞
3. 一行4个整数，数字之间以空格分隔，分别表示：宇宙飞船初始位置的x坐标、初始位置的y坐标、目的地的x坐标、目的地的y坐标
4. 若需要考虑虫洞，一行5个整数，数字之间以空格分隔，分别表示：该虫洞的一个入口x坐标、y坐标、另一个入口的x坐标、y坐标、从当前虫洞的一个入口旅行到另一个入口所需的时间
5. 若需要考虑多个虫洞，重复4
6. 若需要考虑多个情况，重复2-5

输入限制：
1. 情况数T满足，00

输入示例：
4  // 需要考虑3种情况
0  // 情况1，0个虫洞
0 0 60 60  // 初始位置(0,0)，目的地(60,60)
1  // 情况2，1个虫洞
0 0 5 5  // 初始位置(0,0)，目的地(5,5)
1 1 4 4 2  // 虫洞入口1坐标(1,1)，入口2坐标(4,4)，旅行时间花费2单位
1  // 情况3，1个虫洞
0 0 10 2  // 初始位置(0,0)，目的地(10,2)
1 1 4 4 3  // 虫洞入口1坐标(1,1)，入口2坐标(4,4)，旅行时间花费3单位
3  // 情况4，3个虫洞
500 500 1000 1000  // 初始位置(500,500)，目的地(1000,1000)
501 501 999 999 1000  // 虫洞入口1坐标(501,501)，入口2坐标(999,999)，旅行时间花费1000单位
1 1 499 499 100  // 虫洞入口1坐标(1,1)，入口2坐标(499,499)，旅行时间花费100单位
999 999 0 0 200  // 虫洞入口1坐标(999,999)，入口2坐标(0,0)，旅行时间花费200单位

输出示例：
#1 120
# 2 6
#3 12
# 4 306

解释：（作者注：三星系统上没有给出）
1. 情况一中，没有虫洞，因此直接计算时间
2. 情况二中，有一个虫洞，且通过虫洞的时间相比直接移动更快，因此时间为2+2+2=6
3. 情况三中，有一个虫洞，但是通过虫洞后的总计时长相比不通过慢，为2+3+8=13，因此时间为12
4. 情况四中，有三个虫洞，但虫洞一所花费的时间太长，不选择通过，而先通过虫洞二，再通过虫洞三的时间耗费最短，为2+100+2+200+2

判题限制：C、C++、Java 1000ms，Python 15s。内存限制128MB，栈大小限制1MB。50case需全部通过。

#找工作的破防时刻# #牛客创作赏金赛# #笔试# #笔试客户端# #笔试真题# #笔试挂#