← 返回题目列表

AtCoder · icpc2013spring_g

G. 最小成本流的复仇

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

问题陈述

弗洛拉是一只自由职业信鸽。 由于她是一羽优秀的鸽子,所以对她的任务要求太多了。 不可能完成所有任务,所以她决定将部分任务外包给工业信鸽公司。

有 N 城市编号从 0 到 N-1。 她要外包的任务是承载 f 来自城市的货运单位 s 前往城市 t。 有 M 公司里有鸽子。 的 i第 只鸽子从城市运送货物 s_i to t_i,以及持有成本 u 单位是 u a_i if u 小于或等于 d_i,否则 d_i a_i + (u-d_i)b_i。 请注意 i-th 鸽子不能从城市携带 t_i to s_i。 每只鸽子可以携带任意数量的货物。 如果鸽子多次载运货物,则按其所载运货物的总重量计算费用。

Flora 希望最小化总成本。 请计算一下她的最低成本。


输入

测试用例以包含五个整数的行开始 N (2 \leq N \leq 100), M (1 \leq M \leq 1{,}000), s (0 \leq s \leq N-1), t (0 \leq t \leq N-1)和 f (1 \leq f \leq 200)。 你可能会假设 s \neq t。 接下来的每一个 M 行包含五个整数 s_i (0 \leq s_i \leq N-1), t_i (0 \leq t_i \leq N-1), a_i (0 \leq a_i \leq 1{,}000), b_i (0 \leq b_i \leq 1{,}000)和 d_i (1 \leq d_i \leq 200)。 各指定 i第羽鸽子的信息。 你可以假设最多有一对 a_i 和 b_i 满足 a_i < b_i,所有其他都满足 a_i > b_i.

输出

打印最低携带费用 f 来自城市的货运单位 s 前往城市 t 一行。 如果无法携带,请打印“不可能”(为了清楚起见,加引号)。

示例输入 1

2 2 0 1 5
0 1 3 0 3
0 1 2 1 6

样本输入 1 的输出

9

示例输入 2

4 4 0 3 5
0 1 3 0 3
1 3 3 0 3
0 2 2 1 6
2 3 2 1 6

样本输入 2 的输出

18

示例输入 3

2 1 0 1 1
1 0 1 0 1

样本输入 3 的输出

Impossible

示例输入 4

2 2 0 1 2
0 1 5 1 2
0 1 6 3 1

样本输入 4 的输出

9

示例输入 5

3 3 0 2 4
0 2 3 4 2
0 1 4 1 3
1 2 3 1 1

样本输入 5 的输出

14