← 返回题目列表

AtCoder · past19_m

M. DAG 游戏

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

问题陈述

你被给予 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 同时累积分数。

  1. 让 i 是当前块的顶点数。 添加点 P_i 顶点的 i 给他的分数。
  2. If i=N,他结束了游戏 成功.
  3. 如果没有从顶点出发的边 i,他结束了游戏 失败。 否则,选择从顶点出发的边 i.
  4. 让 j 是所选边的编号。 将每个顶点的点乘以边的衰减 j。 换句话说,让 P_i \leftarrow P_i\times W_j 对于每个 i\ (1\leq i\leq N).
  5. 将棋子移动到顶点 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,游戏进行如下。

  1. 添加点 P_1=2 顶点的 1 给他的分数。
  2. 从顶点出发的边之间 1,选择边缘 1.
  3. 将每个顶点的点乘以衰减 W_1=0.5 边缘的 1。 现在, P=(1,2.5,1.5,0.5).
  4. 将棋子移动到顶点 V_1=3.
  5. 添加点 P_3=1.5 顶点的 3 给他的分数。
  6. 从顶点出发的边之间 3,选择边缘 4.
  7. 将每个顶点的点乘以衰减 W_4=0.5 边缘的 4。 现在, P=(0.5,1.25,0.75,0.25).
  8. 将棋子移动到顶点 V_4=4.
  9. 添加点 P_4=0.25 顶点的 4 给他的分数。
  10. 他成功结束了比赛。

在本例中,最终得分为 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