← 返回题目
题库练习 牛奶路由
← 上一题 下一题 →

A2200 | 牛奶路由

来源USACO / 2012
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

农民约翰的农场有一套老旧的管网，管网由M条管道(1<=M<=500)构成，用于将牛奶从谷仓运到储奶罐。 他想在明年移除和更新大部分管道，但他想原封不动地保留一条完整的路径，这样他仍然可以把牛奶从谷仓输送到储罐。

管网由N个节点(1<=N<=500)组成，每个点都可以作为一组管道的端点。结点1是谷仓，结点N是储罐。M条双向管道中的每一条都连接一对节点，并且都有一个延迟值(牛奶达到管的另一端的用时)和容量值(单位时间内可以稳定通过管道的牛奶量)。多条管道可以连接同一对节点。

对于一条连接谷仓与储罐的路径，路径的延迟等于沿途所有管道的延迟之和，路径的容量等于沿途管道最小的容量(因为这是制约牛奶运送的“瓶颈”)。如果约翰通过一条延迟为L、容量为C的管道运送X个单位的牛奶，需要的时间为L+X/C。

给出约翰的管网结构，请帮助他选择一条路径，使得他从谷仓到储罐运送X个单位牛奶的总时间最少。

输入格式

第1行：三个空格分隔的整数:N M X(1<=X<=1000000)。

第2行到第M+1行：每一行描述一条管道，有4个整数：I J L C。I和J(1<=I,J<=N)是这条管道连接的两个点。L和C(1<=L，C<=1000000)是这条管道的延迟和容量。

输出格式

第1行:约翰沿着一条路径送牛奶花费的最少的时间，向下取整到最近的整数。

输入输出样例

输入 #1
3 3 15 
1 2 10 3 
3 2 10 2 
1 3 14 1
输出 #1
27
C++ 编辑器
输入
输出