A115474.单向配送
普及+/提高
官方
通过率:0%
时间限制:1.00s
内存限制:512MB
题目描述
平面上有 n 个投递点,第 i 个投递点坐标为 (xi,yi)。
骑手从起点 (Ax,Ay) 出发,最后需要到达终点 (Bx,By)。在整个过程中,他只能执行下面三种移动:
- (x,y)→(x+1,y)
- (x,y)→(x,y+1)
- (x,y)→(x,y−1)
每移动一次耗时 1,在投递点停下交付不额外耗时。
要求他在途中访问所有投递点至少一次,然后到达终点。已知一定存在可行路线。
请你求出最短总时间。
输入格式
第一行一个整数 t,表示测试组数。
对于每组数据:
- 第一行五个整数 n,Ax,Ay,Bx,By;
- 第二行 n 个整数 x1,x2,…,xn;
- 第三行 n 个整数 y1,y2,…,yn。
输出格式
对每组数据输出一个整数,表示最短时间。
输入输出样例
输入#1
4 1 2 3 5 2 4 4 3 1 3 5 2 3 4 3 5 4 1 6 1 2 7 3 5 2 3 5 5 3 6 4 3 1 4 1 5 6 9 8 6 7 7 7 7 7 3 1 8 8 3
输出#1
6 13 19 15
说明/提示
数据范围
- 1≤t≤104
- 1≤n≤2×105
- 1≤Ax,Ay,Bx,By≤109
- Ax<xi<Bx
- 1≤yi≤109
- 所有测试组的 n 之和不超过 2×105