CF553E Kyoya and Train

鳳鏡夜想要乘火车去上学。有 $n$ 个火车站和 $m$ 条从一个车站到另一个车站的有向单行线。鳳鏡夜现在在 $1$ 号车站，学校在 $n$ 号车站。乘坐火车时，他需要支付车票价，并且火车到达目的地也需要一定时间。然而，每趟火车所需的时间不是固定的，而是随机的。如果鳳鏡夜到达学校时恰好超过 $t$ 个时间单位，他需要缴纳 $x$ 的罚款。 每条火车线由票价和该火车耗时的概率分布描述。更具体地，第 $i$ 条火车线的票价为 $c_i$，其概率分布 $p_{i,k}$ 表示这趟火车会花费 $k$ 个时间单位的概率（$1 \leq k \leq t$）。鳳鏡夜乘坐的每趟火车所需时间都是相互独立的（即使他多次乘坐同一条火车线，每次所需的时间也是独立的）。 鳳鏡夜希望以期望花费最少的价格（包括票价和可能发生的罚款）到达学校。当然，鳳鏡夜始终会采取最优路线，每次到达一个车站后，会根据剩余时间重新规划路线。请你计算——如果鳳鏡夜每步都作出最优选择，他到达学校的期望总花费是多少？

输入的第一行包含四个整数 $n,m,t,x$（$2 \leq n \leq 50$，$1 \leq m \leq 100$，$1 \leq t \leq 20000$，$0 \leq x \leq 10^{6}$）。 接下来的 $2m$ 行描述火车线路。对于每个 $1 \leq i \leq m$： 第 $2i$ 行包含三个整数 $a_i,b_i,c_i$，表示有一条从 $a_i$ 号车站到 $b_i$ 号车站且票价为 $c_i$ 的有向火车线（$1 \leq a_i,b_i \leq n$，$a_i \neq b_i$，$0 \leq c_i \leq 10^6$）。任意两个车站之间每个方向至多有一条火车。 第 $2i+1$ 行包含 $t$ 个整数 $p_{i,1},p_{i,2},\ldots,p_{i,t}$，其中 $p_{i,k}/100000$ 表示这列火车耗时 $k$ 个时间单位的概率（$0 \leq p_{i,k} \leq 100000$，$\sum_{k=1}^t p_{i,k} = 100000$）。 保证从每一个车站到学校都至少有一条通路。

输出一个实数，代表到达学校的最小期望总花费。只要答案的相对或绝对误差不超过 $10^{-6}$ 即视为正确。

第一组样例的最优策略如下： 首先乘坐第一条线路。以概率 $1/2$ 鳳鏡夜会花 $1$ 个时间单位，否则会花 $3$ 个时间单位。 如果火车只用了 $1$ 单位时间，接着他乘坐第 $4$ 条线路。那么他能及时到校的概率是 $1/2$。否则，如果乘坐火车用了 $3$ 单位时间，则他接着乘坐第 $2$ 条线路，此时能及时到校的概率是 $1/10$。 由于所有线路的票价均为零，我们只须考虑罚款概率。发生罚款的概率是 $1/2 \times 1/2 + 1/2 \times 9/10 = 7/10$。可以证明没有比这更优的策略。 第二组样例的最优策略是无论如何都走 $1 \rightarrow 2 \rightarrow 4$。罚款概率是 $3/4$，车票总花费 $200$，所以期望花费为 $200.75$。 由 ChatGPT 5 翻译