当前没有测试数据。

3.小绿小蓝

题目描述

魔王城是一个有向图，王座厅位于$S$号顶点，出口位于$T$号顶点，点$i$有$a_{i}$个怪物，同时通过第$j$条边的时间为$b_{j}$秒。

由于等级上限为$1k$然而小蓝只有$96$级，他希望找到一条从王座厅到出口的路径，使平均每秒钟遇到的怪物最少。

请注意，王座厅与出口处没有怪物（$a_{s}=a_{t}=0$），且如果小蓝在迷宫里面转了太长时间，小绿就会怀疑他，所以小蓝每个点最多经过一次。

为了防止精度误差，你只需输出$3$位小数（四舍五入）。

输入格式

第一行两个整数$N$，$M$。

第二行$N$个整数$a_{i}$。

第三行到第$2+M$行，每行表示一条有向边（$x_{i}$，$y_{i}$，$b_{i}$），分别表示起点，终点，花费的时间（均为整数）。保证不会有自环，但不保证不会有重边。

最后一行两个整数$S$，$T$。

输出格式

一个三位小数，表示答案（请不要输出三位以上，本题没有$spj$），若不足三位请在后面补上$0$。

数据范围与提示

对于$100\%$的数据：

• $2 \leq N \leq 17$
• $M \leq 512$
• $1 \leq S$，$T \leq n$
• $S \neq T$
• $0 \leq a_{i} \leq 10^{4}$
• $1 \leq b_{i} \leq 10^{4}$
• $1 \leq x_{i}$，$y_{i} \leq n$

保证从$S$到$T$有至少一条合法路径。 保证不会有自环。

样例

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

0.684

见castle2.in

见castle2.ans