Description

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$.

Input Format

• 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 Format

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

100.0 2.0
2
1.0 0.0
2.0 1.0
1 2
0 0
0.0 0.0
2.0 2.0

202.8284

Hint

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