#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
using namespace std;
using ll = long long;
const int mn = 1e5+5;
using pll = pair<ll, ll>;
using minpq = priority_queue<pll, vector<pll>, greater<pll>>;

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

ll cost(vector<pll> x, vector<pll> y) {
	ll best = 1e18;
	LineContainer l;
	for (int i = 0; i < x.size(); i++) {
		auto [y1, x1] = x[i];
		l.add(-(-2*y1), -(y1*y1 + 2*x1));
	}
	for (int j = 0; j < y.size(); j++) {
		auto [y2, x2] = y[j];
		best = min(best, -l.query(y2) + 2*x2 + y2*y2);
	}
	return best;
}

ll h[mn];
vector<int> adj[mn];
ll from[mn], to[mn];
bool vis[mn];
int main() {
	ll n, m, s, t; cin >> n >> m >> s >> t;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
		from[i] = 5e18;
		to[i] = 5e18;
	}
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	minpq q;
	q.push({0, s});
	from[s] = 0;
	while (q.size()) {
		auto [d, v] = q.top();
		q.pop();
		if (vis[v]) continue;
		vis[v] = true;
		for (auto x : adj[v]) {
			if (vis[x]) continue;
			ll y = d + (h[x]-h[v])*(h[x]-h[v]);
			if (from[x] > y) {
				from[x] = y;
				q.push({y, x});
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		vis[i] = false;
	}
	q.push({0, t});
	to[t] = 0;
	while (q.size()) {
		auto [d, v] = q.top();
		q.pop();
		if (vis[v]) continue;
		vis[v] = true;
		for (auto x : adj[v]) {
			if (vis[x]) continue;
			ll y = d + (h[x]-h[v])*(h[x]-h[v]);
			if (to[x] > y) {
				to[x] = y;
				q.push({y, x});
			}
		}
	}

	ll ans = 5e18;
	for (int i : adj[s]) {
		ans = min(ans, 2*to[i]);
	}
	for (int i : adj[t]) {
		ans = min(ans, 2*from[i]);
	}
	for (int i = 1; i <= n; i++) {
		vector<pll> x, y;
		for (int j : adj[i]) {
			x.push_back({h[j], from[j]});
			y.push_back({h[j], to[j]});
		}
		ans = min(ans, cost(x, y));
	}
	cout << ans/2;
	if (ans%2) cout << ".5";
	else cout << ".0";
	cout << endl;
}

answer.code: In member function ‘ll LineContainer::query(ll)’:
answer.code:37:17: error: ‘assert’ was not declared in this scope
   37 |                 assert(!empty());
      |                 ^~~~~~
answer.code:6:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
    5 | #include <climits>
  +++ |+#include <cassert>
    6 | using namespace std;