#1070. 「USACO 2012.12 Silver」Milk Routing

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
mroute.in ≫ mroute.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

约翰农场的牛奶输送网络由 条管道()组成,这些管道用于将牛奶从牛棚输送到牛奶储存罐。他计划在未来一年内移除并更新大部分管道,但希望保留一条完整的管道路径,以便仍能将牛奶从牛棚输送到储存罐。

该管道网络由 个连接点()描述,每个连接点可以作为一组管道的端点。连接点 是牛棚,连接点 是储存罐。每条双向管道连接一对连接点,并具有相关的延迟(牛奶从管道一端到达另一端所需的时间)和容量(在稳定状态下每单位时间可以通过管道输送的牛奶量)。同一对连接点之间可以有多条管道连接。

对于从牛棚到储存罐的管道路径,路径的延迟是路径上各管道延迟的总和,路径的容量是路径上各管道容量的最小值(因为这是限制牛奶通过路径的整体速率的「瓶颈」)。如果约翰想通过一条延迟为 、容量为 的管道路径输送总量为 的牛奶,则所需时间为

给定约翰的管道网络结构,请帮助他选择一条从牛棚到储存罐的路径,使他能够在最短的总时间内输送 单位的牛奶。

输入格式 mroute.in

行:
三个用空格分隔的整数: ()。

行到第 行:
每行描述一条管道,包含 个整数:
() 是管道连接的两个连接点。
() 分别是管道的延迟和容量。

输出格式 mroute.out

仅有一行、一个整数:
约翰沿着一条路径送牛奶所花费的最少时间(向下取整到最近的整数)。

样例

输入 #1

3 3 15 
1 2 10 3 
3 2 10 2 
1 3 14 1

输出 #1

27

数据范围与提示

约翰想通过他的管道网络输送 单位的牛奶。管道 连接连接点 (牛棚)和连接点 ,延迟为 ,容量为 。管道 也以类似的方式定义。

路径 需要 单位的时间。路径 需要 单位的时间,因此是最优的。 (由 ChatGPT 4o 翻译)