引路归家

最后一批平民从东区涌来——老人、孩子、抱婴儿的女人。他们的衣服破了，脸灰了，但眼睛还亮着。

"往哪走？"一个老人问你。

"西门。"你说，"那边安全。"

"多远？"

"三公里。"你说，"但要绕路——中间有塌方，不能直走。"

"绕哪？"

你展开地图。东区到西区有三条路：一条直道（塌方了），一条北线（长但稳），一条南线（短但有哨塔）。

"北线。"你说，"长一点，但安全。"

"太长。"老人说，"孩子走不动。"

"那南线？"

"有哨塔。"CC说，"会开枪。"

"那就拆哨塔。"

"拆？"CC看着你，"你拆？"

"我拆。"你说，"你们走南线，我拆哨塔，然后追上你们。"

"不行。"Echo说，"分头行动，信号会断。"

"那一起走南线？"

"会被打。"

"那就——"你想了想，"分批。老人孩子走北线，年轻人走南线。南线的人先拆哨塔，然后接北线的人。"

"时间？"

"北线两小时。南线一小时拆塔，一小时接人。"你说，"总共三小时，所有人到西区。"

CC看着你，眼神变了——不是怀疑，是认可。

"你越来越像指挥官了。"她说。

"我不是指挥官。"你说，"我只是会算。"

"算？"

"对。"你说，"这就是一道题——从起点到终点，多条路径，不同限制，求最短时间把所有点送到终点。"

Echo把路线投影出来——蓝线是北线，红线是南线，绿线是汇合点。

"第一批。"她说，"南线突击队，出发。"

CC站起来，把数据刀插回腰间。

"我带队。"她说。

"你？"

"我跑得快。"她说，"拆塔这种事，我来。"

题目描述

$n$ 个人要从东区撤离到西区。有若干条路径，每条路径有不同长度和不同容量（最多同时走多少人）。求把所有人送到西区的最短时间。

输入格式

$n, m, s, t$。然后 $m$ 条边 $(u, v, w, c)$，$w$ 为长度，$c$ 为容量。

输出格式

最短时间。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 多源点多汇点网络流问题。
• 拆成超级源连所有起点，超级汇连所有终点。
• 用最小费用最大流，费用为时间，容量为人数限制。

"出发了。"CC说。

"小心。"你说。

"放心。"她说，"我跑得快，子弹追不上。"

她带着五个人走了。你看着他们的背影消失在转角，心跳得很快。

"她会回来的。"Echo说。

"我知道。"你说。

"你知道？"

"她知道有人等她。"你说，"所以她会回来。"

Echo安静了很久。

"等。"她说，"这是一个很强的理由。"

"对。"你说，"是最强的理由。"

[第三题：布设哨兵]