3745. 迷宫

单点时限: 1.0 sec

内存限制: 512 MB

“不出门就是为抗疫做贡献”

响应国家的号召,Cuber QQ 决定设计一款游戏让大家在家自我隔离的日子不再无聊。

游戏中玩家所要完成的任务是,帮助 $m$ 名误入迷宫的青少年逃脱困境。

游戏中的迷宫用有向图 $G=\langle V, E \rangle$ 表示,迷宫只有唯一的出口,为顶点 $T$ ,青少年闯入的地方为顶点 $S$, $S\in V$, $T\in V$ 。

迷宫中白天是一片漆黑的,只有晚上才会点亮灯,因此这群少年只能每天晚上行动。青少年们并不一定要一起行动,他们可以根据玩家的想法独立行动。

每天晚上玩家可以控制他们可以呆在原地不动或选择移动到下一个顶点(从一个顶点到相邻顶点恰好需要花费一个晚上时间),当然,玩家可以控制每一个青年有不一样的选择。

当然,游戏不会这么简单,Cuber QQ 认为一个好的游戏既要有乐趣,又要有一定的难度。所以 Cuber QQ 规定游戏地图中的每条边 $e\in E $ 都有一个容量 $c(e)$ ,代表着在同一个晚上最多 $ c(e)$ 个青少年可以穿过该边。

现在游戏要求玩家在最少的时间内帮助所有青少年到达迷宫的出口 $T$ ,Cuber QQ 自然需要知道这个时间是多少了,你能帮助他解决吗?

输入格式

输入数据第一行包含五个整数 $m$, $V$, $E$, $S$, $T$ ($1\le m,V\le 50$, $1\le E\le 1000$, $1\le S,T\le V,S\neq T$) ,分别表示被困的人数、迷宫的顶点数量和迷宫的边数。

接下来的 $E$ 行,每行三个整数 $x$, $y$, $c(e)$ ($1\le x,y\le V$, $1\le c(e)\le m$) ,表示迷宫中有一条从 $x$ 到 $y$ 的边,这条边每个晚上最多允许 $c(e)$ 个青少年通过。

保证给出的图,至少存在一条路径能从 $S$ 到 $T$ 。

输出格式

输出数据包含一个整数,表示所有人逃离迷宫最少需要的天数。

样例

Input
2 3 2 1 3
1 2 1
2 3 1
Output
3

33 人解决,82 人已尝试。

43 份提交通过,共有 327 份提交。

6.2 EMB 奖励。

创建: 6 月,2 周前.

修改: 6 月,2 周前.

最后提交: 1 月,2 周前.

来源: EOJ Monthly 2020.3

题目标签