P4579 [FJOI2018] Postman Problem

Since $\text{2010}$, the online shopping market has developed rapidly, and courier companies have become a key part of making transactions successful. Xiao Guo is an SF Express courier. His salary mainly includes a basic wage, delivery commission, pickup commission, other benefits and subsidies, etc. For each completed parcel order, Xiao Guo can usually get a commission of $10\%$ of the shipping fee. Therefore, the more orders he completes and the faster he completes them, the higher his income will be. Xiao Guo is responsible for all courier services on $2$ parallel streets in the city. On these $2$ parallel streets, there are $2$ courier stations. Each delivery route starts from one station, and after delivering all parcels, ends at the other station. To finish the task efficiently, Xiao Guo wants to use the shortest route to complete all deliveries. That is, given the distance between the $2$ parallel streets, the positions of the $2$ stations, and the positions of all delivery points, Xiao Guo needs to compute the shortest route that starts from one station, delivers all parcels, and finally returns to the other station. The street distance means the vertical distance between the $2$ parallel streets. If we set the $x$ axis parallel to the streets, and the leftmost positions on both streets have $x=0$, then any position on the $2$ streets can be represented by the straight-line distance from the leftmost end of the street to that position, i.e., the $x$ coordinate value of that position. For example, suppose the street distance between streets A and B is $2$. The two stations $S_1$ and $S_2$ are located at street A, $x=1$, and street B, $x=3$, respectively. There are also $2$ delivery points $T_1$ and $T_2$ located at street A, $x=3$, and street B, $x=1$, respectively, as shown in the figure. Xiao Guo’s task is to start from station $S_1$, deliver the parcels at $T_1$ and $T_2$, and then return to the other station $S_2$. Programming task: given the street distance of the $2$ parallel streets, the positions of the $2$ stations, and the positions of all delivery points, compute the shortest route that starts from one station, delivers all parcels, and ends at the other station.

The first line contains two positive integers $n,m$, $1 \le n,m \le 10000$, representing the number of positions on the two parallel streets A and B (including delivery points and station positions). The positions are numbered as A: $1,2,\ldots,n$; B: $1,2,\ldots,m$. The second line contains four positive integers $a,b,c,d$, indicating that the two station positions are $(a,b)$ and $(c,d)$. $a=0$ or $c=0$ means the corresponding station is on street $A$, and $a=1$ or $c=1$ means the corresponding station is on street $B$. $b$ and $d$ represent the position indices of the stations on the corresponding streets. For example, $(a,b)=(0,3)$ means the first station is on street $A$, and its position is the $3$-rd among the given $n$ positions of street $A$. The third line contains one real number $h$, representing the street distance between the $2$ parallel streets $(1 \le h \le 10)$. The fourth line contains $n$ real numbers, representing the $x$ coordinates of the $n$ positions on street $A$ $(1 \le x < 20000)$. The fifth line contains $m$ real numbers, representing the $x$ coordinates of the $m$ positions on street $B$ $(1 \le x < 20000)$.

Output the computed shortest route length, rounded to $2$ decimal places.

For $10\%$ of the testdata, $n,m\le 8$. For $30\%$ of the testdata, $n,m\le 100$. For $50\%$ of the testdata, $n,m\le 1000$. For $100\%$ of the testdata, $n,m\le 10000$. Translated by ChatGPT 5