P15619 [ICPC 2022 Jakarta R] City Hall

You are the mayor of ICPC City. The city has $N$ intersections, numbered from $1$ to $N$, where intersection $i$ has an altitude of $H_i$. Your house is at intersection $S$, while the city hall is at intersection $T$. There are $M$ two-way roads, numbered from $1$ to $M$, that connect the intersections. Road $i$ directly connects intersections $U_i$ and $V_i$. Each pair of intersections can only be directly connected by at most one road. The roads connect such that each intersection can be visited from any other intersections by traversing one or more roads. Every morning, you cycle from your house to the city hall. Suppose that you are traversing a road that directly connects intersections $u$ and $v$. The energy that you spend to traverse that road is $(H_u - H_v)^2$. The total energy required for a path is the sum of energy that is spent traversing each road in that path. As a mayor, you are allowed to change the altitude of **at most** one intersection to any non-negative real number. Using this opportunity, you want to minimize the total energy required to cycle from your house to the city hall.

Input begins with $4$ integers $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$). The next line contains $N$ integers $H_i$ ($0 \leq H_i \leq 100\,000$) representing the altitude of intersection $i$. Each of the next $M$ lines contains $2$ integers $U_i$ $V_i$ ($1 \leq U_i < V_i \leq N$) representing the intersections directly connected by road $i$. Each pair of intersections can only be directly connected by at most one road. Furthermore, the roads connect such that each intersection can be visited from any other intersections by traversing one or more roads.

Output a real number in a single line representing the minimum total energy required. Your answer is considered correct if its **absolute error** does not exceed $10^{-6}$.

#### Explanation for the sample input/output #1 To get the minimum total required energy, you should change the altitude of intersection $2$ to $6.5$. Then, cycling route $1 \rightarrow 2 \rightarrow 3$ requires a total energy of $(5 - 6.5)^2 + (8 - 6.5)^2 = 4.5$. #### Explanation for the sample input/output #2 To get the minimum total required energy, you can choose either intersection $3$ or intersection $4$ and change its altitude to $3$. #### Explanation for the sample input/output #3 The cycling route $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ requires a total energy of $0$ as all its intersections are at the same height. Changing any intersection's height will not decrease the total energy required.