E - Average Score of Tourist Routes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は旅行プランナーです。ある観光エリアには N 個の観光スポットがあり、それぞれ 1 から N までの番号が付けられています。これらのスポット同士を結ぶ双方向の道路が M 本あります。

各観光スポット i には満足度 c_i が設定されています。高橋君は、観光スポット S を出発してスポット T に到着する観光ルートを提案したいと考えています。

ここで、観光ルートとは、S から T への単純パス、すなわちスポットの列 S = v_0, v_1, \ldots, v_k = T（k \geq 1）であって、以下の条件を全て満たすものです。

  • 列に含まれるスポットは全て異なる（同じスポットを 2 回以上訪れない）。
  • 連続する 2 つのスポット v_{i-1} と v_i（1 \leq i \leq k）の間に道路が存在する。

観光ルートのスコアを、そのルート上で訪れる全てのスポット（始点 S と終点 T を含む）の満足度の総和 \displaystyle\sum_{i=0}^{k} c_{v_i} と定義します。

S から T への全ての観光ルートについてスコアを計算したとき、その平均値（スコアの総和を観光ルートの総数で割った値）を求めてください。

なお、S から T への観光ルートが少なくとも 1 つ存在することが保証されます。

制約

  • 2 \leq N \leq 18
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • S \neq T
  • 1 \leq c_i \leq 1000（1 \leq i \leq N）
  • 1 \leq u_j < v_j \leq N（1 \leq j \leq M）
  • 同じスポットの組を結ぶ道路は高々 1 本である（多重辺はない）
  • 自己ループはない
  • S から T への単純パスが少なくとも 1 つ存在する
  • 入力は全て整数である

入力

入力は以下の形式で与えられます。

N M S T
c_1
c_2
\vdots
c_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

1 行目に、観光スポットの数 N、道路の数 M、出発スポットの番号 S、到着スポットの番号 T がスペース区切りで与えられます。

続く N 行のうち i 行目（1 \leq i \leq N）に、スポット i の満足度 c_i が与えられます。

続く M 行のうち j 行目（1 \leq j \leq M）に、2 つの整数 u_j, v_j がスペース区切りで与えられ、スポット u_j とスポット v_j が双方向の道路で結ばれていることを表します。各道路について u_j < v_j を満たします。

出力

S から T への全ての観光ルートにおけるスコアの平均値を小数で 1 行に出力してください。真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされます。

入力例 1

3 2 1 3
10
20
30
1 2
2 3

出力例 1

60.000000000000000

入力例 2

4 4 1 4
5
8
6
7
1 2
2 4
1 3
3 4

出力例 2

19.000000000000000

入力例 3

6 8 1 6
4
9
7
3
8
10
1 2
1 3
2 4
3 4
2 5
4 5
4 6
5 6

出力例 3

31.714285714285715

入力例 4

10 16 1 10
12
7
15
9
20
5
11
14
8
13
1 2
1 3
1 4
2 5
2 6
3 5
3 7
4 6
4 7
5 6
5 8
6 8
6 9
7 8
7 9
8 10

出力例 4

87.619047619047620

入力例 5

2 1 1 2
1
1000
1 2

出力例 5

1001.000000000000000

Score : 466 pts

Problem Statement

Takahashi is a travel planner. A certain sightseeing area has N tourist spots, numbered from 1 to N. There are M bidirectional roads connecting these spots.

Each tourist spot i has a satisfaction value c_i. Takahashi wants to propose a sightseeing route that starts at spot S and arrives at spot T.

Here, a sightseeing route is a simple path from S to T, that is, a sequence of spots S = v_0, v_1, \ldots, v_k = T (k \geq 1) satisfying all of the following conditions:

  • All spots in the sequence are distinct (no spot is visited more than once).
  • For each pair of consecutive spots v_{i-1} and v_i (1 \leq i \leq k), a road exists between them.

The score of a sightseeing route is defined as the sum of satisfaction values of all spots visited along the route (including the starting spot S and the ending spot T): \displaystyle\sum_{i=0}^{k} c_{v_i}.

Compute the average score over all sightseeing routes from S to T (i.e., the sum of scores of all routes divided by the total number of routes).

It is guaranteed that at least one sightseeing route from S to T exists.

Constraints

  • 2 \leq N \leq 18
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • S \neq T
  • 1 \leq c_i \leq 1000 (1 \leq i \leq N)
  • 1 \leq u_j < v_j \leq N (1 \leq j \leq M)
  • There is at most one road between any pair of spots (no multi-edges)
  • There are no self-loops
  • At least one simple path from S to T exists
  • All input values are integers

Input

The input is given in the following format:

N M S T
c_1
c_2
\vdots
c_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

The first line contains the number of tourist spots N, the number of roads M, the starting spot number S, and the destination spot number T, separated by spaces.

In the following N lines, the i-th line (1 \leq i \leq N) contains the satisfaction value c_i of spot i.

In the following M lines, the j-th line (1 \leq j \leq M) contains two integers u_j and v_j separated by a space, indicating that spots u_j and v_j are connected by a bidirectional road. Each road satisfies u_j < v_j.

Output

Output in a single line the average score over all sightseeing routes from S to T as a decimal number. The answer will be considered correct if the absolute or relative error from the true value is at most 10^{-6}.

Sample Input 1

3 2 1 3
10
20
30
1 2
2 3

Sample Output 1

60.000000000000000

Sample Input 2

4 4 1 4
5
8
6
7
1 2
2 4
1 3
3 4

Sample Output 2

19.000000000000000

Sample Input 3

6 8 1 6
4
9
7
3
8
10
1 2
1 3
2 4
3 4
2 5
4 5
4 6
5 6

Sample Output 3

31.714285714285715

Sample Input 4

10 16 1 10
12
7
15
9
20
5
11
14
8
13
1 2
1 3
1 4
2 5
2 6
3 5
3 7
4 6
4 7
5 6
5 8
6 8
6 9
7 8
7 9
8 10

Sample Output 4

87.619047619047620

Sample Input 5

2 1 1 2
1
1000
1 2

Sample Output 5

1001.000000000000000