也是水管

[题目描述]

这道题也是水管…如果你没有见过第一道水管的话,那是一道因为我的zz而废掉的好题…我这次就跟水管过不去了.

我们有n个容量无限的水箱,以及m条连接水箱之间的单向水管,一开始1号水箱里有无限的水,保证1号水箱可以到达所有水箱且没有水箱连向1号水箱,且任何水箱可以到达n号水箱且n号水箱不连向任何水箱,保证这是一个有向无环图.

一条水管有4个参数$u_i,v_i$分别表示水管的起点和终点,$c_i$表示在当$u_i$号水箱里的水达到$c_i$的量时水管才会开启,开始以$w_i$每单位时间的速度从$u_i$往$v_i$输水,当$u_i$号水箱里的水低于$c_i$的量时,水管会立刻关闭,水管的长度可以忽略,即可以认为水管一开启$u_i$里的水就会开始被移动到$v_i$号水箱里.

求当n号水箱的体积达到C时的时间,保证答案$\leq 10^9$

[输入格式]

第一行三个正整数n,m,C

第2~m+1行每行四个正整数表示$u_i,v_i,c_i,w_i$

[输出格式]

一行一个浮点数,表示n号水箱的体积达到C的时间,你可以输出任意位精度,当你的答案与标准答案的差的绝对值小于$2\times 10^{-3}$时你的答案被认为是正确的

[样例输入]

 

[样例输出]

[数据范围]

对于100%的数据,$2\leq n\leq 1000,n-1\leq m\leq 20000$

$1\leq u_i,v_i\leq n,0\leq c_i,w_i\leq 10^9,1\leq C\leq 10^9$

保证不存在$i\neq j$且$u_i=u_j$且$c_i=c_j$

//这道题复杂度不对…

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注