问题陈述
你被给予 N- 顶点 M-边简单有向图。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 j 从顶点定向 U_j 到顶点 V_j。 每个顶点都有一个整数属性 点:顶点的点 i is P_i。 此外,每条边都有一个真实的属性 腐烂 之间 0 和 1:边缘的衰减 j is W_j。 保证给定的图不存在闭环。 (换句话说,没有办法从一个顶点出发 i 沿边返回顶点 i.)
Takahashi 将在此图上玩一个游戏。 最初,顶点 1 上面有一块,高桥的分数是 0。 他执行以下步骤将棋子移动到顶点 N 同时累积分数。
- 让 i 是当前块的顶点数。 添加点 P_i 顶点的 i 给他的分数。
- If i=N,他结束了游戏 成功.
- 如果没有从顶点出发的边 i,他结束了游戏 失败。 否则,选择从顶点出发的边 i.
- 让 j 是所选边的编号。 将每个顶点的点乘以边的衰减 j。 换句话说,让 P_i \leftarrow P_i\times W_j 对于每个 i\ (1\leq i\leq N).
- 将棋子移动到顶点 V_j,然后跳转到步骤 1。
判断他能否成功结束游戏。 如果可能的话,打印游戏的最大可能的最终得分。
约束
- N,M,P_i,U_j,和 V_j 是整数。
- 2\leq N \leq 10^5
- 1\leq M \leq 10^5
- 1\leq P_i\leq 10^4
- U_j \neq V_j
- (U_j,V_j)\neq (U_k, V_k)\ (j\neq k)
- 0\leq W_j\leq 1
- W_j 是的倍数 10^{-6} 并给出六位小数。
- 给定的图没有有向循环。
输入
输入由标准输入按以下格式给出:
N M P_1 P_2 \dots P_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
输出
如果他能够成功结束游戏,则打印最大可能的最终得分,并且 -1 否则。
在前一种情况下,如果与真实值的绝对或相对误差最多为,则您的答案被认为是正确的 10^{−6}.
示例输入 1
4 4 2 5 3 1 1 3 0.500000 1 2 0.250000 2 3 0.250000 3 4 0.500000
示例输出 1
3.7500000000
我们表示序列 (P_1,P_2,P_3,P_4) 只需通过 P。 最初, P=(2,5,3,1).
如果他沿着顶点移动棋子 1\rightarrow 3\rightarrow 4,游戏进行如下。
- 添加点 P_1=2 顶点的 1 给他的分数。
- 从顶点出发的边之间 1,选择边缘 1.
- 将每个顶点的点乘以衰减 W_1=0.5 边缘的 1。 现在, P=(1,2.5,1.5,0.5).
- 将棋子移动到顶点 V_1=3.
- 添加点 P_3=1.5 顶点的 3 给他的分数。
- 从顶点出发的边之间 3,选择边缘 4.
- 将每个顶点的点乘以衰减 W_4=0.5 边缘的 4。 现在, P=(0.5,1.25,0.75,0.25).
- 将棋子移动到顶点 V_4=4.
- 添加点 P_4=0.25 顶点的 4 给他的分数。
- 他成功结束了比赛。
在本例中,最终得分为 2+1.5+0.25=3.75,这是最大可能的。
示例输入 2
3 1 1 1 1 1 2 0.000000
示例输出 2
-1
他无法成功结束游戏。
示例输入 3
6 12 22 75 26 45 72 81 4 6 0.185514 3 6 0.758252 2 3 0.622989 2 4 0.984614 1 3 0.465086 1 5 0.396959 5 3 0.618272 5 2 0.016128 1 2 0.869673 1 4 0.363219 2 6 0.097935 5 4 0.877468
示例输出 3
138.6258141601