#P2656. 采蘑菇

    ID: 1661 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论洛谷原创SPFA强连通分量缩点

采蘑菇

题目描述

小胖和 ZYR 要去 ESQMS 森林采蘑菇。

ESQMS 森林间有 NN 个小树丛,MM 条小径,每条小径都是单向的,连接两个小树丛,上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次,可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土,所以一条路上的蘑菇被采过后,又会长出一些新的蘑菇,数量为原来蘑菇的数量乘上这条路的“恢复系数”,再下取整。

比如,一条路上有 44 个蘑菇,这条路的“恢复系数”为 0.70.7,则第一~四次经过这条路径所能采到的蘑菇数量分别为 4,2,1,04,2,1,0

现在,小胖和 ZYR 从 SS 号小树丛出发,求他们最多能采到多少蘑菇。

输入格式

第一行两个整数,NNMM

第二行到第 M+1M+1 行,每行四个数,分别表示一条小路的起点,终点,初始蘑菇数,恢复系数。

M+2M+2 行,一个整数 SS

输出格式

一行一个整数,表示最多能采到多少蘑菇,保证答案不超过 (2311)(2^{31}-1)

3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1
8

提示

对于 30%30\% 的数据,N7N\le 7M15M\le15

另有 30%30\% 的数据,满足所有“恢复系数”为 00

对于 100%100\% 的数据,1N8×1041 \le N\le 8\times 10^41M2×1051\le M\le 2\times 10^50恢复系数0.80\le\text{恢复系数}\le 0.8 且最多有一位小数, 1SN1\le S\le N