← 返回题目列表

AtCoder · icpc2015autumn_j

J. 最长最短路径

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

问题陈述

给定一个有向图和两个节点 $s$ 和 $t$。给定的图可以包含同一节点对之间的多条边,但不能包含自环。 每条边 $e$ 都有其初始长度 $d_e$ 和成本 $c_e$。 您可以通过支付费用来扩大优势。 形式上,将边 $e$ 的长度从 $d_e$ 更改为 $d_e + x$ 需要花费 $x \cdot c_e$。 (请注意,$x$ 可以是非整数。) 边缘不能缩短。

您的任务是通过延长成本 $P$ 内的一些边来最大化从节点 $s$ 到节点 $t$ 的最短路径的长度。您可以假设至少有一条从 $s$ 到 $t$ 的路径。


输入

输入由单个测试用例组成,格式如下。

$N$ $M$ $P$ $s$ $t$
$v_1$ $u_1$ $d_1$ $c_1$
...
$v_M$ $u_M$ $d_M$ $c_M$

第一行包含五个整数 $N$、$M$、$P$、$s$ 和 $t$:$N$ ($2 \leq N \leq 200$) 和 $M$ ($1\leq M \leq 2{,}000$) 分别是给定图的节点和边的数量, $P$ ($0 \leq P \leq 10^6)$ 是你可以支付的成本限额,$s$ 和 $t$ ($1 \leq s, t \leq N$, $s \neq t$) 分别是目标路径的起始和结束节点。 以下$M$行中的每一行包含四个整数$v_i$、$u_i$、$d_i$和$c_i$,这意味着从$v_i$到$u_i$有一条边($1\leq v_i、u_i\leq N$、$v_i\neq u_i$),初始长度为$d_i$($1\leq d_i \leq 10$)和成本$c_i$ ($1 \leq c_i \leq 10$)。

输出

通过延长成本$P$内的一些边,输出从节点$s$到节点$t$的最短路径的最大长度。 输出可以包含不超过 $10^{-6}$ 的绝对或相对误差。



示例输入 1

3 2 3 1 3
1 2 2 1
2 3 1 2

样本输入 1 的输出

6.0000000

示例输入 2

3 3 2 1 3
1 2 1 1 
2 3 1 1
1 3 1 1

样本输入 2 的输出

2.5000000

示例输入 3

3 4 5 1 3
1 2 1 2
2 3 1 1
1 3 3 2
1 3 4 1

样本输入 3 的输出

4.2500000