1. 题意理解

• 有两条平行街道 A 和 B，相距为 $h$。
• 每条街道上有若干位置（用 $x$ 坐标表示，$x \ge 0$）。
• 有两个工作站，分别位于 $(a,b)$ 和 $(c,d)$，其中 $a=0$ 表示在 A 街，$a=1$ 表示在 B 街；$b$ 是位置编号（不是 $x$ 坐标，需要查表）。
• 所有投递点（任务点）的位置已知，分布在 A 街和 B 街的某些位置上。
• 快递员从一个工作站出发，访问所有投递点（每个点一次），最后到达另一个工作站。
• 求最短路径长度。

---

2. 关键点

1. 位置编号与坐标
   输入中第 4 行是 A 街 $n$ 个位置的 $x$ 坐标，第 5 行是 B 街 $m$ 个位置的 $x$ 坐标。
   工作站和投递点用位置编号表示，需要转成 $x$ 坐标。

2. 街道间移动
   在同一个位置（相同 $x$ 坐标）可以从 A 街到 B 街，距离为 $h$（垂直距离）。
   在同一条街上，从 $x_1$ 到 $x_2$ 的距离是 $|x_1 - x_2|$。

3. 问题本质
   这是带起点终点、访问所有点的最短路径问题，但所有点分布在两条平行线上。

---

3. 问题抽象

设：

• $A[1..n]$ 为 A 街的 $x$ 坐标。
• $B[1..m]$ 为 B 街的 $x$ 坐标。
• 所有投递点集合 $P$ 分布在 $A$ 和 $B$ 中。
• 起点 $S$ 和终点 $E$ 是两个工作站。

我们要找一条路径 $S \to p_1 \to p_2 \to \dots \to p_k \to E$，覆盖 $P$ 中所有点，且总长度最小。

---

4. 观察结构

因为街道是平行的，路径可以这样分解：

1. 在 A 街上从左到右或从右到左移动。
2. 在 B 街上从左到右或从右到左移动。
3. 在某个 $x$ 坐标处切换街道。

最优路径一定是在两条街道之间交替覆盖投递点，并且每次切换街道时，选择合适的位置以最小化总路程。

---

5. 动态规划思路

这是一个经典的双线 TSP 变种（起点终点固定，访问所有任务点）。

我们可以定义：

$dp[i][j][0]$ 表示已经覆盖了 A 街前 $i$ 个任务点和 B 街前 $j$ 个任务点，且当前在 A 街的最小路程。

$dp[i][j][1]$ 表示已经覆盖了 A 街前 $i$ 个任务点和 B 街前 $j$ 个任务点，且当前在 B 街的最小路程。

但这里“前 $i$ 个”需要先对每条街上的任务点按 $x$ 坐标排序。

---

6. 状态转移

设：

• $A'$ = A 街上所有任务点的 $x$ 坐标（排序后）。
• $B'$ = B 街上所有任务点的 $x$ 坐标（排序后）。
• $n_A = |A'|$，$n_B = |B'|$。

初始化：

• 起点可能在 A 或 B 街，需要分别初始化。

转移：

• 从 $dp[i][j][0]$ 到 $dp[i+1][j][0]$：在 A 街上从 $A'[i]$ 走到 $A'[i+1]$。
• 从 $dp[i][j][0]$ 到 $dp[i][j+1][1]$：从 A 街 $A'[i]$ 到 B 街 $B'[j+1]$，距离 $=\sqrt{h^2 + (A'[i]-B'[j+1])^2}$。
• 从 $dp[i][j][1]$ 到 $dp[i+1][j][0]$：从 B 街 $B'[j]$ 到 A 街 $A'[i+1]$，距离 $=\sqrt{h^2 + (B'[j]-A'[i+1])^2}$。
• 从 $dp[i][j][1]$ 到 $dp[i][j+1][1]$：在 B 街上从 $B'[j]$ 走到 $B'[j+1]$。

最后加上到终点的距离。

---

7. 起点终点处理

起点 $S$ 和终点 $E$ 可能不在任务点中，需要作为第 0 个点和最后一个点加入 DP。

我们可以：

• 将起点视为第一个访问的点，终点视为最后一个访问的点。
• 因为起点和终点固定，我们可以分别尝试两种顺序：$S$ 在 A 或 B，$E$ 在 A 或 B，但题目已给它们的位置。

更简单的方法：

• 在 DP 初始化时，如果起点在 A 街，则 $dp[1][0][0] = \text{从起点到 } A'[1]$ 的距离；如果起点在 B 街，则 $dp[0][1][1] = \text{从起点到 } B'[1]$ 的距离。
• 在 DP 结束后，加上最后位置到终点的距离。

---

8. 样例验证

样例输入：

2 2
0 1 1 2
2
1 3
1 3

解释：

• n=2, m=2
• 工作站1: (0,1) 表示 A 街第 1 个位置，$x=1$
• 工作站2: (1,2) 表示 B 街第 2 个位置，$x=3$
• h=2
• A 街坐标: [1, 3]
• B 街坐标: [1, 3]

投递点：题目没说哪些是投递点？
这里可能默认所有位置都是投递点？但工作站也是位置，可能不算投递点？
样例似乎假设 A 街位置1和 B 街位置1是起点终点，A 街位置3和 B 街位置3是投递点。

路径： 起点 A1(1) → A3(3) → 切换到 B3(3) → B1(1) 终点。

距离： A1→A3: |3-1| = 2
A3→B3: 垂直距离 h=2
B3→B1: |1-3| = 2
总 = 2+2+2 = 6，但样例输出 6.83，说明中间切换不是垂直，而是斜线。

实际上： A1(1) → B1(1): 距离 2（垂直）
B1(1) → A3(3): 距离 $\sqrt{2^2 + (3-1)^2} = \sqrt{4+4} = \sqrt{8} \approx 2.828$
A3(3) → B3(3): 距离 2（垂直）
总 ≈ 2 + 2.828 + 2 = 6.828 ≈ 6.83

所以样例路径可能是：起点 A1 → B1 → A3 → B3（终点）。

---

9. 最终算法

1. 读入数据，将位置编号转成 $x$ 坐标。
2. 确定起点 $S$ 和终点 $E$ 的坐标和街道。
3. 收集所有投递点（除去起点终点？题目没明确，可能需要看起点终点是否在任务列表中，一般起点终点不是任务点）。
4. 对 A 街和 B 街上的任务点分别按 $x$ 排序。
5. 用 DP：
   • 状态 $dp[i][j][street]$。
   • 初始化：如果起点在 A，且 A 有任务点，则 $dp[1][0][0] = |S_x - A'[1]|$；如果起点在 B，且 B 有任务点，则 $dp[0][1][1] = |S_x - B'[1]|$；如果起点所在街无任务点，则可能需要先跨街。
   • 转移如上所述。
   • 答案 = $\min(dp[n_A][n_B][0] + \text{到终点的距离}, dp[n_A][n_B][1] + \text{到终点的距离})$，其中到终点的距离要考虑街道切换。
6. 输出保留两位小数。

---

10. 总结

本题是双线 TSP 的变种，用动态规划解决，状态为两街上已访问的任务点数量和当前所在街道，转移时考虑同街移动和跨街移动（用勾股定理计算斜边距离）。