← 返回题目列表

AtCoder · awc0066_e

E. 旅游线路平均分

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥是一名旅行策划师。某个观光区有 N 旅游景点,编号自 1 to N。有 M 连接这些地点的双向道路。

各旅游点 i 有满意度值 c_i。高桥想提出一条从景点开始的观光路线 S 并到达现场 T.

这里,观光路线是 简单路径 来自 S to T,即一系列斑点 S = v_0, v_1, \ldots, v_k = T (k \geq 1) 满足以下所有条件:

  • 序列中的所有点都是不同的(没有点被访问超过一次)。
  • 对于每对连续点 v_{i-1} 和 v_i (1 \leq i \leq k),他们之间有一条路。 一条观光路线的

的 分数 定义为该路线上所有游览点(包括起始点)的满意度值之和 S 和结局点 T): \displaystyle\sum_{i=0}^{k} c_{v_i}.

计算所有观光路线的平均得分 S to T (即所有路线的分数总和除以路线总数)。

保证至少有一条观光线路 S to T 存在。

约束

  • 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)
  • 任意一对点之间最多有一条路(无多边)
  • 没有自环
  • 至少一条简单路径 S to T 存在
  • 所有输入值均为整数

输入

输入按以下格式给出:

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

第一行包含旅游点数量 N, 道路数量 M,起始点编号 S,以及目的地点编号 T,用空格分隔。

如下 N 行, i- 第行 (1 \leq i \leq N) 包含满意度值 现货 c_i 现货的 i.

如下 M 行, j- 第行 (1 \leq j \leq M) 包含两个整数 u_j 和 v_j 以空格分隔,表示斑点 u_j 和 v_j 由双向道路连接。每条路都满足 u_j < v_j.

输出

在一行中输出从 S to T 作为十进制数。如果与真实值的绝对或相对误差最多为,则答案将被认为是正确的 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