EOJ Monthly 2020.3

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

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

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

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

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

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

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

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