P15619 [ICPC 2022 Jakarta R] City Hall

你是 ICPC 市的市长。该市有 $N$ 个交叉路口，编号从 $1$ 到 $N$，其中交叉路口 $i$ 的海拔为 $H_i$。你的家位于交叉路口 $S$，而市政厅位于交叉路口 $T$。 市内有 $M$ 条双向道路，编号从 $1$ 到 $M$，用于连接这些交叉路口。道路 $i$ 直接连接交叉路口 $U_i$ 和 $V_i$。每对交叉路口之间最多只能由一条道路直接连接。道路的连接方式保证了从任何一个交叉路口出发，都可以通过遍历一条或多条道路到达任何其他交叉路口。 每天早晨，你都会骑自行车从家前往市政厅。假设你正在遍历一条直接连接交叉路口 $u$ 和 $v$ 的道路，那么你通过该道路所消耗的能量为 $(H_u - H_v)^2$。一条路径所需的总能量，就是该路径上遍历每条道路所消耗的能量之和。 作为市长，你被允许将**最多**一个交叉路口的海拔更改为任意非负实数。利用这个机会，你希望最小化从家骑自行车到市政厅所需的总能量。

输入以 $4$ 个整数 $N$ $M$ $S$ $T$ 开始（$2 \leq N \leq 100\,000$；$N - 1 \leq M \leq \min(\frac{N(N-1)}{2}, 200\,000)$；$1 \leq S, T \leq N$；$S \neq T$）。下一行包含 $N$ 个整数 $H_i$（$0 \leq H_i \leq 100\,000$），表示交叉路口 $i$ 的海拔。 接下来的 $M$ 行，每行包含 $2$ 个整数 $U_i$ $V_i$（$1 \leq U_i < V_i \leq N$），表示由道路 $i$ 直接连接的交叉路口。每对交叉路口之间最多只能由一条道路直接连接。此外，道路的连接方式保证了从任何一个交叉路口出发，都可以通过遍历一条或多条道路到达任何其他交叉路口。

在一行中输出一个实数，表示所需的最小总能量。只要你的答案的**绝对误差**不超过 $10^{-6}$，即被视为正确。

#### 样例输入/输出 #1 的解释 为了获得所需的最小总能量，你应该将交叉路口 $2$ 的海拔更改为 $6.5$。那么，骑行路线 $1 \rightarrow 2 \rightarrow 3$ 所需的总能量为 $(5 - 6.5)^2 + (8 - 6.5)^2 = 4.5$。 #### 样例输入/输出 #2 的解释 为了获得所需的最小总能量，你可以选择交叉路口 $3$ 或交叉路口 $4$，并将其海拔更改为 $3$。 #### 样例输入/输出 #3 的解释 骑行路线 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ 所需的总能量为 $0$，因为该路线上所有交叉路口的海拔都相同。更改任何交叉路口的海拔都不会减少所需的总能量。 翻译由 DeepSeek 完成