BZPRO
#5208. [Jsoi2017]税收
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
JSOI王国的交通网络可以看成是一个N个点M条边的带权有向图。图中每个顶点代表一个城市，每条边代表连接两个
城市的道路，同一对城市之间可能有多条道路连接。每条道路i有两个权值Di,和Ci，分别表示它的初始税收和在这
条道路上增加1单位的税收所需要承受的民众不满意程度。一条路径的税收是路径上所有道路的税收之和。
国王JS想要尽可能地增加从城市s到t旅行的税收，但这并不是个简单的事情。JSOI的民众非常聪明，无论你如何调
整税收，他们只会走从s到t的税收总和最小的路径，而另一方面，如果调整税收导致的不满意程度之和超过某个值
p将会引发社会危机。因此，JYY需要在承受的不满意程度之和不超过p的情况下使s到t的税收总和最小的路径的税
收尽可能地大。需要注意的是，JYY不能减少某条道路的税收，但他可以对任意道路增加任意实数单位的税收。
输入格式
第一行包含五个整数，分别为N,M,P,S,T
接下来M行，每行四个整数Ui,Vi,Di,Ci描述一条从Ui,到Vi,的有向边
初始税收是Di,，每增加一单位的税收带来的不满意程度是Ci。
1≤N≤200,1≤M≤2×10O00,1≤P≤1000000
1≤Ci,Di≤10。保证至少存在一条从s到t的合法路径。
输出格式
输出一行一个实数，表示可能的s到t的最大税收。
与标准答案误差在10^-4以内即认为正确。
样例
样例输入
3 2 3 1 3
1 2 2 1
2 3 1 2
样例输出
6.000000
数据范围与提示
BZPRO