雷电爆裂之力

2023-10-18 16:50

文章标签 爆裂雷电之力

本文主要是介绍雷电爆裂之力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

听说导体切割磁感线可以发电？

今天，zhuaiballl想要做切割磁感线运动，感受雷电的力量。

南北方向有四条马路，从西到东依次是京师路，木铎路，金声路和新街口外大街，可以看成是四条平行的数轴，且相邻的两条数轴之间距离为1m。东西走向有许多小道连接了相邻的马路。假设地磁南极和地理北极重合，地磁北极和地理南极重合。现在zhuaiballl位于京师路的某个位置，想要出发前往新街口外大街，速度为1m/s。由于可能没有一条路径从西到东一直连向新街口外大街，所以每次遇到丁字路口时，zhuaiballl需要选择是往左走还是往右走，样例如下图所示。

zhuaiballl想要感受尽可能强的雷电力量，所以希望从他开始往东走时开始，到他到达新街口外大街所需要的时间尽可能短。

现在，给你附近的地图，你能否求出从zhuaiballl开始往东走时开始，到他到达新街口外大街的最短时间？

Input

第一行是一个正整数 $T(\leq 20)$ ，表示测试数据的组数，

对于每组测试数据，

第一行是一个整数 $n,m,k(1\leq n,m,k \leq 100000)$ ，分别表示连接京师路与木铎路，木铎路与金声路，金声路与新街口外大街的道路个数，

第二行包含个以空格分隔的整数 a_1,a_2,...,a_n ，表示连接京师路与木铎路的各个小道的南北方向坐标（单位：m），

第三行包含个以空格分隔的整数 b_1,b_2,...,b_m ，表示连接木铎路与金声路的各个小道的南北方向坐标（单位：m），

第四行包含个以空格分隔的整数 c_1,c_2,...,c_k ，表示连接金声路与新街口外大街的各个小道的南北方向坐标（单位：m），

保证每行坐标按严格递增的顺序给出，并且坐标绝对值不超过 10^9 。

Output

对于每组测试数据，输出一行，包含一个整数，表示答案（单位：s）。

Sample Input

Sample Output

Source

第十六届北京师范大学程序设计竞赛决赛

Author

#include<algorithm>
#include<iostream>
#include<queue>
#include<cstdio>
#include<climits>using namespace std;const int N = 100000 + 5;
using LL = long long;
LL a[N], b[N], B[N], c[N], C[N];
int n, m, k;struct node{LL x, sum, s;node(LL x, LL sum, LL s){this -> x = x;this -> sum = sum;this -> s = s;}bool operator < (const node & m) const {return sum > m.sum;}
};queue<node> Q;void DFS(){for(int i = 0; i < n; i++){Q.push((node){a[i], 1, 1});}while(!Q.empty()){node t = Q.front(); Q.pop();if(t.s == 1){LL *p = lower_bound(b, b + m, t.x);int tt = distance(b, p);if(tt < m - 1){LL y = b[tt+1];LL sum = t.sum + abs(t.x - y);if(sum < B[tt+1]){Q.push((node){y, sum + 1, 2});B[tt+1] = sum;}}if(tt != m){LL y = b[tt];LL sum = t.sum + abs(t.x - y);if(sum < B[tt]) {B[tt] = sum;Q.push((node){y, sum + 1, 2});}}if(tt != 0){LL y = b[tt-1];LL sum = t.sum + abs(t.x - y);if(sum < B[tt-1]) {B[tt-1] = sum;Q.push((node){y, sum + 1, 2});}}}if(t.s == 2){LL *p = lower_bound(c, c + k, t.x);int tt = distance(c, p);if(tt < k-1){LL y = c[tt + 1];LL sum = t.sum + abs(t.x - y);if(sum < C[tt + 1]){C[tt + 1] = sum + 1;}}if(tt != k){LL y = c[tt];LL sum = t.sum + abs(t.x - y);if(sum < C[tt]) {C[tt] = sum + 1;}}if(tt != 0){LL y = c[tt-1];LL sum = t.sum + abs(t.x - y);if(sum < C[tt-1]) {C[tt-1] = sum + 1;}}}}LL *p = min_element(C, C + k);cout << *p << endl;
}
int main(){int T;scanf("%d", &T);while(T --){for(int i = 0; i < N; i++) B[i] = C[i] = ((LL)1 << 40);scanf("%d %d %d", &n, &m, &k);for(int i = 0; i < n; i++) scanf("%lld", &a[i]);for(int i = 0; i < m; i++) scanf("%lld", &b[i]);for(int i = 0; i < k; i++) scanf("%lld", &c[i]);DFS();}
}