P1907 设计道路

Caesar 远征高卢回来后，对你大加赞赏，他亲自来到 Genoa 视察。 Genoa 在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road 和 Rome Road。两个路口间只可能是其中一种道路。在 Rome Road 上可以驾驶马车，而在 Dirt Road 上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用 Rome Road 连接起来。 现在 Caesar 已经到达码头，他要求去你家参观。Caesar 有一个癖好，喜欢坐车而不喜欢走路。所以 Caesar 走 Dirt Road 时的不满值要比走 Rome Road 时大。 为了不让 Caesar 过于不满而罢免你的职位，请设计路线使得 Caesar 的不满值最小。

给定一张二维平面上 $n+2$ 个结点的无向完全图（也就是说，每两个点之间都有一条边），其中 $i$ 号点的坐标为 $A_i(x_i,y_i)$。 无向图中有两种边，一种叫 Rome Road，一种叫 Dirt Road。 记所有 Rome Road 的集合为 $S$，$l(X,Y)$ 表是线段 $XY$ 的长度，则一条边 $(A_i,A_j)$ 的边权为： $$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}$$ 即该边的长度与对应系数（Rome Road 为 $d_R$，Dirt Road 为 $d_D$）的乘积。 保证所有与 $n+1$ 号结点和 $n+2$ 号结点相连的所有边都是 Dirt Road。 现在，你需要求出 $n+1$ 号结点和 $n+2$ 号结点之间的最短路。

第一行两个小数 $d_D,d_R$。 第二行一个正整数 $n$。 下面 $n$ 行，第 $i$ 行两个小数 $x_i,y_i$。 下面若干行（以 `0 0` 为结束标志），每行两个正整数 $u,v$，表示边 $(u,v)$ 是 Rome Road。 下面一行两个小数 $x_{n+1},y_{n+1}$。 最后一行两个小数 $x_{n+2},y_{n+2}$。

求出 $n+1$ 号结点和 $n+2$ 号结点之间的最短路，答案保留 $4$ 位小数。

对于 $100\%$ 的数据： - $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$ - Rome Road 不超过 $200$ 条 - $1 \le u,v \le n$（结束标志除外） - $u \ne v$ 其中 $p(X)$ 表示小数 $X$ 的小数位数。