#4898. [Apio2017]商旅

			
4 5 2

10 9 5 2

6 4 20 15

9 7 10 9

-1 -1 16 11

1 2 3

2 3 3

1 4 1

4 3 1

3 1 1

			
2

在样例中，我们考虑下面两条环路，“1 - 2 - 3 - 1” 和 “1 - 4 - 3 - 1”。

考虑环路 “1 - 2 - 3 - 1” ：这条环路消耗的总时间是 分钟。在这条环路中，

最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5 ）；在编号

为 2 的集市中卖出编号为 2 的商品（得到的金钱为 15 ），然后立即购买编号为 1 的商品

（花费的金钱为 6 ）；带着编号为 1 的商品经过编号为 3 的集市，在回到编号为 1 的城市后

卖出（得到的金钱为 9 ）。在这个环路中，总盈利为13。 这个环路的盈利效率为13/7 ，向下取整后为 1 。

考虑环路 “1 - 4 - 3 - 1” ：这条环路消耗的总时间是 分钟。在这条环路中，

最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5 ）；在编号

为 4 的集市中卖出编号为 2 的商品（得到的金钱为 11 ）；然后经过编号为 3 的集市回到编

号为 1 的城市。在这个环路中，总盈利为 6。 这个环路的盈利效率为6/3 ，向下取整后为 2 。

综上所述，盈利效率最高的环路的盈利效率为 2 。