P1907 Design Roads

After Caesar returned from his expedition to Gaul, he praised you highly and personally came to inspect Genoa. Under your construction, Genoa has become extremely prosperous. With increased fiscal revenue, you built a transportation system for the city. Ancient Roman transportation consists of two types of roads—Dirt Road and Rome Road. Between any two intersections, the road is of exactly one type. Carriages can run on Rome Roads, but not on Dirt Roads. Building roads is a massive project, so you could not connect the entire city with Rome Roads. Now Caesar has arrived at the dock and wants to visit your home. Caesar has a quirk: he prefers riding to walking. Therefore, his dissatisfaction on Dirt Roads is higher than on Rome Roads. To avoid getting dismissed by making Caesar too dissatisfied, please design a route that minimizes Caesar’s dissatisfaction.

You are given an undirected complete graph with $n+2$ nodes on a 2D plane (that is, every pair of points is connected by an edge). The coordinates of node $i$ are $A_i(x_i, y_i)$. There are two types of edges in the undirected graph: Rome Road and Dirt Road. Let the set of all Rome Road edges be $S$, and let $l(X, Y)$ denote the length of segment $XY$. Then the weight of an edge $(A_i, A_j)$ is: $$c(A_i,A_j)=\begin{cases}d_R \cdot l(A_i,A_j),&(A_i,A_j) \in S\\d_D \cdot l(A_i,A_j),&(A_i,A_j) \notin S\end{cases}$$ That is, the length of the edge times the corresponding coefficient ($d_R$ for Rome Road, $d_D$ for Dirt Road). All edges incident to nodes $n+1$ and $n+2$ are guaranteed to be Dirt Roads. Now, you need to find the shortest path between nodes $n+1$ and $n+2$.

- The first line contains two decimals $d_D, d_R$. - The second line contains a positive integer $n$. - The next $n$ lines: on the $i$-th line, two decimals $x_i, y_i$. - Then several lines (terminated by `0 0`), each containing two positive integers $u, v$, indicating that edge $(u, v)$ is a Rome Road. - The next line contains two decimals $x_{n+1}, y_{n+1}$. - The last line contains two decimals $x_{n+2}, y_{n+2}$.

Output the length of the shortest path between nodes $n+1$ and $n+2$, with $4$ digits after the decimal point.

Constraints (for $100\%$ of the testdata): - $0.1 \le d_R < d_D \le 10^3$. - $0 \le p(d_D), p(d_R) \le 1$. - $1 \le n \le 10^3$. - $0 \le x_i, y_i \le 10^4$. - $0 \le p(x_i), p(y_i) \le 2$. - The number of Rome Road edges does not exceed $200$. - $1 \le u, v \le n$ (excluding the end marker). - $u \ne v$. Here $p(X)$ denotes the number of digits after the decimal point of decimal $X$. Translated by ChatGPT 5