← 返回题目列表

Codeforces · 553/E

E. 京也和火车

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

Kyoya Ootori 想坐火车去学校。有n个火车站和m条在各个车站之间行驶的单程火车线路。 Kyoya 目前在火车站 1,学校在车站 n。坐火车必须买票,而且火车也需要一定的时间。然而,火车并不完美,到达目的地的时间是随机的。如果 Kyoya 严格晚于 t 个时间单位到达学校,他将需要支付 x 的罚款。

每条火车线路都由票价和火车所需时间的概率分布来描述。更正式地说,火车线路 i 的车票成本为 ci,概率分布 pi, k 表示该火车在所有 1 ≤ k ≤ t 条件下占用 k 个时间单位的概率。 Kyouya 使用的每列火车所花费的时间是相互独立的随机值(此外,如果 Kyoya 多次乘坐同一列火车,则火车可能会花费不同的时间,并且这些时间也是彼此独立的)。

Kyoya 希望花最少的钱去学校(票价加上可能迟到的罚款)。当然,Kyoya 对于如何去学校有一个最优的计划,每次到达火车站时,他都可能会根据剩余时间重新计算自己的计划。如果 Kyoya 采取最佳行动,他上学所需的预计费用是多少?

输入

输入的第一行包含四个整数 n、m、t、x (2 ≤ n ≤ 50, 1 ≤ m ≤ 100, 1 ≤ t ≤ 20 000, 0 ≤ x ≤ 106)。

接下来的 2m 行包含列车的描述。

第 2i 行将有 3 个整数 ai、bi、ci,表示从 ai 车站到 bi 的单程火车,票价为 ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 106)。从任何车站到学校都至少有一条路径。

第 (2i + 1) 行将包含 t 个整数 pi, 1, pi, 2, ..., pi, t,其中 pi, k / 100000 是该列车需要 k 单位时间穿越的概率(0 ≤ pi, k ≤ 100 000,对于 1 ≤ k ≤ t, $$\sum_{k=1}^{t} p_{i,k} = 100000$$)。

保证每个方向每对站台之间的列车数量不超过一列。

输出

打印一个实数,该实数等于上学的最佳预期成本。如果答案的相对误差或绝对误差不超过 10 - 6,则认为答案是正确的。

示例

输入 #1

4 4 5 1
1 2 0
50000 0 50000 0 0
2 3 0
10000 0 0 0 90000
3 4 0
100000 0 0 0 0
2 4 0
0 0 0 50000 50000

输出 #1

0.7000000000

输入 #2

4 4 5 1
1 2 100
50000 0 50000 0 0
2 3 100
10000 0 0 0 90000
3 4 100
100000 0 0 0 0
2 4 100
0 0 0 50000 50000

输出 #2

200.7500000000

注意

第一种情况的最优策略如下:

首先,沿着第一条火车线行驶。 Kyoya 有 1 / 2 的概率需要 1 个时间单位。否则,Kyoya 将花费 3 个时间单位。

如果火车需要 1 个时间单位,则沿第 4 条火车线路行驶。 Kyoya 将以 1 / 2 的概率准时到达学校。否则,如果火车需要 3 个时间单位,则沿第 2 条火车线路行驶。 Kyoya 能按时到校的概率是十分之一。

由于所有列车线路的成本都是零,我们可以只看 Kyoya 受到处罚的概率。 Kyoya 必须支付罚金的概率是 1 / 2 × 1 / 2 + 1 / 2 × 9 / 10 = 7 / 10。我们可以证明没有其他策略是绝对更好的。

第二种情况的最优策略是无论如何都沿着 1 → 2 → 4 行驶。 Kyoya 将以 3 / 4 的概率受到处罚,火车的成本为 200,因此预期成本为 200.75。