分数: 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