P5837 [USACO19DEC] Milk Pumping G

Farmer John recently bought a new farm in order to expand his milk industry empire. This new farm is connected to a nearby town by a network of pipelines, and FJ wants to find the best set of pipelines to buy and use to transport milk from the farm to the town. This pipeline network can be described by $N$ junctions (endpoints of pipelines), numbered $1 \ldots N$. Junction $1$ represents FJ's farm, and junction $N$ represents the town. There are $M$ bidirectional pipelines, each connecting two junctions. Using the $i$-th pipeline costs FJ $c_i$ dollars to buy, and it can support a flow rate of $f_i$ liters of milk per second. FJ wants to buy some pipelines that form a single simple path whose endpoints are junction $1$ and junction $N$. The cost of this path is the sum of the costs of all pipelines on the path. The flow rate of the path is the minimum flow rate among all pipelines on the path (because this is the bottleneck when sending milk along the path). FJ wants to maximize the ratio of the path flow rate to the path cost. It is guaranteed that there exists a path from $1$ to $N$.

The first line of input contains $N$ and $M$. The next $M$ lines each describe one pipeline with four integers: $a$ and $b$ (the two different junctions the pipeline connects), $c$ (the cost of the pipeline), and $f$ (the flow rate of the pipeline). Both cost and flow rate are positive integers in the range $1 \ldots 1000$.

Output $10^6$ times the value of the optimal answer, rounded down (that is, if this number is not an integer, output the greatest integer less than it).

In this example, there is only one path from $1$ to $N$. Its flow rate is $\min(3,4)=3$, and its cost is $2+5=7$. ### Constraints Test cases $2 \sim 5$ satisfy $N,M\le 100$. For $100\%$ of the testdata, $2 \leq N \leq 1000$ and $1 \leq M \leq 1000$. Problem by: Brian Dean. Translated by ChatGPT 5