AT_past19_m.DAG ゲーム

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $N$ 个顶点、 $M$ 条边的简单有向图。顶点编号为 $1$ 到 $N$ ，边编号为 $1$ 到 $M$ 。第 $j$ 条边从顶点 $U_j$ 指向顶点 $V_j$ 。每个顶点有一个整数属性 point，第 $i$ 个顶点的 point 为 $P_i$ 。另外，每条边有一个实数属性 decay，取值范围为 $0$ 到 $1$ ，第 $j$ 条边的 decay 为 $W_j$ 。保证该图不存在有向环（即不存在从某个顶点 $i$ 沿着若干条边回到顶点 $i$ 的路径）。

高桥将在这个图上玩一个游戏。起初，顶点 $1$ 上有一个棋子，高桥的分数为 $0$ 。他进行如下操作，将棋子移动到顶点 $N$ ，同时累计分数。

设当前棋子所在顶点编号为 $i$ 。将顶点 $i$ 的 point 值 $P_i$ 加到分数上。
如果 $i=N$ ，则成功结束游戏。
如果 $i$ 没有出边，则失败结束游戏。否则，从 $i$ 出发的边中选择一条。
设选中的是第 $j$ 条边。将所有顶点的 point 值都乘以该边的 decay 值，即对每个 $i$ $(1\leq i\leq N)$ ， $P_i\leftarrow P_i\times W_j$ 。
将棋子移动到顶点 $V_j$ ，跳转回第 1 步。

判断他能否成功结束游戏。如果可以，求游戏过程中分数的最大可能值。

输入格式

输入按以下格式给出：

$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

输入#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

说明/提示

样例解释 1

我们用 $P$ 表示 $(P_1, P_2, P_3, P_4)$ 。初始时 $P=(2,5,3,1)$ 。

若依次走 $1\rightarrow 3\rightarrow 4$ ，过程如下：

把顶点 $1$ 的 point $P_1=2$ 加到分数上。
从 $1$ 出发的边里，选第 $1$ 条边。
所有顶点的 point 都乘以该边的 decay $W_1=0.5$ ，此时 $P=(1,2.5,1.5,0.5)$ 。
棋子移到顶点 $3$ 。
把顶点 $3$ 的 point $P_3=1.5$ 加到分数上。
从 $3$ 出发的边里，选第 $4$ 条边。
所有顶点的 point 都乘上该边的 decay $W_4=0.5$ ，此时 $P=(0.5,1.25,0.75,0.25)$ 。
棋子移到顶点 $4$ 。
把顶点 $4$ 的 point $P_4=0.25$ 加到分数上。
游戏成功结束。

此时最终分数为 $2+1.5+0.25=3.75$ ，为最大可能值。

样例解释 2

无法成功结束游戏。

约束条件

$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) \quad(j\neq k)$
$0\leq W_j\leq 1$
$W_j$ 是 $10^{-6}$ 的倍数，小数点后六位。
给定的图无有向环。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页